题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5044
题意：给一棵树，在点和边上操作
题解：树链剖分，剖完后用树状数组维护即可，因为只有加减操作，连树状的部分都不用写，最后要注意当n等于1的情况
1 #include<cstdio> 2 #pragma comment(linker, "/STACK:1024000000,1024000000") 3 #define F(i,a,b) for(int i=a;i<=b;++i) 4 5 const int N=100010;char op[10]; 6 int t,ic=1,n,m,x,y,c,egu[N],egv[N],g[N],nxt[2*N],v[2*N],ed,dep[N],sz[N],fa[N],hs[N],tid[N],top[N],idx,fid[N],fid2[N]; 7 __int64 a[N],b[N],ans1[N],ans2[N],all; 8 9 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;} 10 11 void dfs1(int u,int pre){ 12 sz[u]=1,fa[u]=pre,hs[u]=0,dep[u]=dep[pre]+1; 13 for(int i=g[u];i;i=nxt[i]){ 14 int vv=v[i]; 15 if(vv!=pre){ 16 dfs1(vv,u); 17 if(sz[vv]>hs[u])hs[u]=vv; 18 sz[u]+=sz[vv]; 19 } 20 } 21 } 22 23 void dfs2(int u,int tp){ 24 tid[u]=++idx,fid[idx]=u,top[u]=tp; 25 if(hs[u])dfs2(hs[u],tp); 26 for(int i=g[u];i;i=nxt[i]){ 27 int vv=v[i]; 28 if(vv!=fa[u]&&vv!=hs[u])dfs2(vv,vv); 29 } 30 } 31 32 void up(__int64*a,int x,int y,int c,int k){ 33 int fx=top[x],fy=top[y]; 34 while(fx!=fy){ 35 if(dep[fx]>dep[fy]) 36 a[tid[fx]]+=c,a[tid[x]+1]-=c,x=fa[fx],fx=top[x]; 37 else a[tid[fy]]+=c,a[tid[y]+1]-=c,y=fa[fy],fy=top[y]; 38 } 39 if(dep[x]>dep[y])x=x^y,y=x^y,x=x^y; 40 a[tid[x]+k]+=c,a[tid[y]+1]-=c; 41 } 42 43 int main(){ 44 scanf("%d",&t); 45 while(t--){ 46 scanf("%d%d",&n,&m); 47 F(i,1,n)g[i]=0;ed=0; 48 F(i,1,n-1)scanf("%d%d",egu+i,egv+i),adg(egu[i],egv[i]),adg(egv[i],egu[i]); 49 dfs1(1,0),idx=0,dfs2(1,1); 50 F(i,1,n)a[i]=0,b[i]=0;all=0; 51 while(m--){ 52 scanf("%s%d%d%d",op,&x,&y,&c); 53 if(op[3]=='1')up(a,x,y,c,0); 54 else up(b,x,y,c,1); 55 } 56 F(i,1,n-1)if(dep[egu[i]]>=dep[egv[i]])fid2[tid[egu[i]]]=i; 57 else fid2[tid[egv[i]]]=i; 58 F(i,1,n)all+=a[i],ans1[fid[i]]=all;all=0; 59 F(i,2,n)all+=b[i],ans2[fid2[i]]=all; 60 printf("Case #%d: ",ic++); 61 F(i,1,n)printf("%I64d%c",ans1[i],i==n?' ':' '); 62 F(i,1,n-1)printf("%I64d%c",ans2[i],(i==n-1?' ':' ')); 63 if(n==1)puts("");//PE 64 } 65 return 0; 66 }