首页 > 代码库 > 树链刨分 HDU 3966

树链刨分 HDU 3966

树 n个点 m条边(其实就是n-1) q个询问

a1 a2 a3 ...

这些节点开始的人

I  a b c   a->b  这条链上的都加c

D    ...                             减

q  a  查询节点a上的人

具体看代码上的注释

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;
#define MAXN 50010
struct edge
{
    int to,w,next;
}x[2*MAXN];
int head[MAXN];
int num[MAXN],siz[MAXN],     top[MAXN], son[MAXN],dep[MAXN],tid[MAXN];
int _tid[MAXN],father[MAXN];
// 权    包括这个点子树节点数 树链的头   重孩子   深度    树链中下标
/ 根据线段树的l找到这个点  父亲
int cnt,n,m,q,tim; void add(int u,int v) //建边   { x[cnt].to=v; x[cnt].next=head[u]; head[u]=cnt++; } void init(int n) { cnt=0; tim=0; memset(head,-1,sizeof(head)); memset(son,0,sizeof(son)); } void dfs1(int u,int fa) { siz[u]=1;//包括这个点的子树的节点数 father[u]=fa; dep[u]=dep[fa]+1; for(int i=head[u];i!=-1;i=x[i].next) { int v=x[i].to; if(v==fa) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[son[u]] < siz[v])//找到重孩子 son[u] = v; } } void dfs2(int u,int tp)// { tid[u]=++tim;// 线段树中的l r  _tid[tim]=u;// 反过来 top[u]=tp; //链的头 if(son[u]!=0)// 在一调链上 就在线段树的连续的一部分 dfs2(son[u],tp); for(int i=head[u];i!=-1;i=x[i].next) { int v=x[i].to; if(v!=father[u]&&v!=son[u])  //既不是父亲也不是重孩子  重新刨分  dfs2(v,v); } } struct node { int l,r,val,lazy; }z[MAXN<<3]; void update(int l,int r,int a1,int b1,int v,int a); void change(int x,int y,int val) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); update(1,n,tid[top[x]],tid[x],val,1);//链头到 这个节点更新 x = father[top[x]]; } if(dep[x] > dep[y]) swap(x,y); update(1,n,tid[x],tid[y],val,1); //最后 } void build(int l,int r,int a) { z[a].l=l; z[a].r=r; z[a].val=z[a].lazy=0; if(l==r) { z[a].val=num[_tid[l]]; return ; } int mid=(l+r)>>1; build(l,mid,a<<1); build(mid+1,r,a<<1|1); } void push_down(int a) { if(z[a].lazy) { z[a<<1].val+=z[a].lazy; z[a<<1|1].val+=z[a].lazy; z[a<<1].lazy+=z[a].lazy; z[a<<1|1].lazy+=z[a].lazy; z[a].lazy=0; } } void update(int l,int r,int a1,int b1,int v,int a) { if(a1<=l&&r<=b1) { z[a].val+=v; z[a].lazy+=v; return ; } push_down(a); int mid=(l+r)>>1; if(a1<=mid) update(l,mid,a1,b1,v,a<<1); if(b1>mid) update(mid+1,r,a1,b1,v,a<<1|1); } int Ques(int l,int r,int x,int a) { push_down(a); if(l==r&&l==x) return z[a].val; int mid=(l+r)>>1; if(x<=mid) return Ques(l,mid,x,a<<1); else return Ques(mid+1,r,x,a<<1|1); } int main() { while(scanf("%d%d%d",&n,&m,&q)!=EOF) { init(n); for(int i=1;i<=n;i++) scanf("%d",&num[i]); while(m--) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,0);// 2个深搜 dfs2(1,1); build(1,n,1);//建树 while(q--) { char s[5]; scanf("%s",s); if(s[0]==Q) { int a; scanf("%d",&a); printf("%d\n",Ques(1,n,tid[a],1)); } else { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(s[0]==I) change(a,b,c); else change(a,b,-c); } } } return 0; }

 

树链刨分 HDU 3966