BZOJ1036 树的统计Count
目录
- BZOJ1036 树的统计Count
- 题解
- ｃｏｄｅ
BZOJ1036 树的统计Count
题目传送门
题解
一道树剖裸题，拿来练练手。。
ｃｏｄｅ
#include
using namespace std;
typedef long long ll;
bool Finish_read;
templateinline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
templateinline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
templateinline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
templateinline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int N=1e5+500;
const int inf=1e7;
#define ls(o) o<<1
#define rs(o) o<<1|1
int n,tot,q;
struct edge {int to,nxt;
}E[N<<2];
int head[N],a[N],v[N],idx[N],dep[N],top[N],fa[N],heav[N],sz[N];
/*==================Define Area================*/
namespace SegmentTree {struct node {int l,r,sz,sum,mx;}t[N<<3];void Update(int o) {t[o].sum=t[ls(o)].sum+t[rs(o)].sum;t[o].mx=max(t[ls(o)].mx,t[rs(o)].mx);}void Build(int o,int l,int r) {t[o].l=l;t[o].r=r;t[o].sz=r-l+1;if(l==r) {t[o].mx=t[o].sum=v[l];return ;}int mid=(l+r)>>1;Build(ls(o),l,mid);Build(rs(o),mid+1,r);Update(o);return ;}void Modify(int o,int pos,int v) {if(t[o].l==t[o].r&&t[o].l==pos) {t[o].sum=t[o].mx=v;return ;}int mid=(t[o].l+t[o].r)>>1;if(mid>=pos) Modify(ls(o),pos,v);else Modify(rs(o),pos,v);Update(o);return ;}int QueryMx(int o,int l,int r) {if(t[o].l>=l&&t[o].r<=r) return t[o].mx;int mid=(t[o].l+t[o].r)>>1;int ans=-inf;if(mid>=l) ans=max(ans,QueryMx(ls(o),l,r));if(mid=l&&t[o].r<=r) return t[o].sum;int mid=(t[o].l+t[o].r)>>1;int ans=0;if(mid>=l) ans+=QuerySum(ls(o),l,r);if(midmxson) {mxson=sz[to];heav[o]=to;}}return ;} int cnt=0;void dfs2(int o,int topp) {idx[o]=++cnt;top[o]=topp;v[cnt]=a[o];if(!heav[o]) return ;dfs2(heav[o],topp);for(int i=head[o];~i;i=E[i].nxt) {int to=E[i].to;if(!idx[to]) dfs2(to,to);} }int TreeSum(int x,int y) {int ans=0;while(top[x]!=top[y]) {if(dep[top[x]]dep[y]) swap(x,y);ans+=QuerySum(1,idx[x],idx[y]);return ans;}int TreeMx(int x,int y) {int ans=-inf;while(top[x]!=top[y]) {if(dep[top[x]]dep[y]) swap(x,y);ans=max(ans,QueryMx(1,idx[x],idx[y]));return ans;}
}
using namespace poufen;void Addedge(int u,int v) {E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;
}int main() {read(n);memset(head,-1,sizeof head);for(int i=1,u,v;i 转载于:https://www.cnblogs.com/Apocrypha/p/9435653.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！