Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3477 Solved: 1085
Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
Source
树链剖分裸题
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define ls l,mid,rt<<1 8 #define rs mid+1,r,rt<<1|1 9 #define LL long long 10 using namespace std; 11 const int mxn=100010; 12 int read(){ 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 int n,m; 19 struct edge{ 20 int v,nxt; 21 }e[mxn<<1]; 22 int hd[mxn],mct=0; 23 void add_edge(int u,int v){ 24 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 25 } 26 struct node{ 27 int w,e; 28 int top,f,son; 29 int size,dep; 30 }tr[mxn]; 31 struct segtree{ 32 LL sum,mk; 33 }st[mxn<<2]; 34 int sz=0; 35 int w[mxn]; 36 void DFS1(int u){ 37 tr[u].size=1;tr[u].son=0; 38 for(int i=hd[u];i;i=e[i].nxt){ 39 int v=e[i].v; 40 if(v==tr[u].f)continue; 41 tr[v].f=u; 42 tr[v].dep=tr[u].dep+1; 43 DFS1(v); 44 tr[u].size+=tr[v].size; 45 if(tr[v].size>tr[tr[u].son].size)tr[u].son=v; 46 } 47 return; 48 } 49 void DFS2(int u,int top){ 50 tr[u].top=top; 51 tr[u].w=++sz; 52 if(tr[u].son){ 53 DFS2(tr[u].son,top); 54 for(int i=hd[u];i;i=e[i].nxt){ 55 int v=e[i].v; 56 if(v!=tr[u].f && v!=tr[u].son){ 57 DFS2(v,v); 58 } 59 } 60 } 61 tr[u].e=sz; 62 return; 63 } 64 void pushdown(int l,int r,int rt){ 65 if(l==r)return; 66 st[rt<<1].mk+=st[rt].mk;st[rt<<1|1].mk+=st[rt].mk; 67 int mid=(l+r)>>1; 68 st[rt<<1].sum+=st[rt].mk*(mid-l+1); 69 st[rt<<1|1].sum+=st[rt].mk*(r-mid); 70 st[rt].mk=0; 71 return; 72 } 73 void add(int L,int R,int v,int l,int r,int rt){ 74 if(L<=l && r<=R){ 75 st[rt].sum+=(LL)v*(r-l+1); 76 st[rt].mk+=v; 77 return; 78 } 79 if(st[rt].mk)pushdown(l,r,rt); 80 int mid=(l+r)>>1; 81 if(L<=mid)add(L,R,v,ls); 82 if(R>mid)add(L,R,v,rs); 83 st[rt].sum=st[rt<<1].sum+st[rt<<1|1].sum; 84 return; 85 } 86 long long qsum(int L,int R,int l,int r,int rt){ 87 if(L<=l && r<=R)return st[rt].sum; 88 if(st[rt].mk)pushdown(l,r,rt); 89 int mid=(l+r)>>1; 90 LL res=0; 91 if(L<=mid)res+=qsum(L,R,ls); 92 if(R>mid)res+=qsum(L,R,rs); 93 return res; 94 } 95 long long findsum(int x){ 96 LL res=0; 97 while(tr[x].top!=1){ 98 res+=qsum(tr[tr[x].top].w,tr[x].w,1,n,1); 99 x=tr[tr[x].top].f; 100 } 101 res+=qsum(1,tr[x].w,1,n,1); 102 return res; 103 } 104 int main(){ 105 n=read();m=read(); 106 int i,j,u,v,op,x,a; 107 for(i=1;i<=n;i++)w[i]=read(); 108 for(i=1;i<n;i++){ 109 u=read();v=read(); 110 add_edge(u,v); 111 add_edge(v,u); 112 } 113 DFS1(1); 114 DFS2(1,1); 115 for(i=1;i<=n;i++) 116 add(tr[i].w,tr[i].w,w[i],1,n,1); 117 /* for(i=1;i<=n;i++) 118 printf("%d ",qsum(tr[i].w,tr[i].w,1,n,1)); 119 printf(" ");*/ 120 for(i=1;i<=m;i++){ 121 op=read(); 122 switch(op){ 123 case 1:{ 124 x=read();a=read(); 125 add(tr[x].w,tr[x].w,a,1,n,1); 126 break; 127 } 128 case 2:{ 129 x=read();a=read(); 130 add(tr[x].w,tr[x].e,a,1,n,1); 131 break; 132 } 133 case 3:{ 134 x=read(); 135 printf("%lld ",findsum(x)); 136 break; 137 } 138 } 139 } 140 return 0; 141 }