题意：给一棵树，并给定各个点权的值，然后有3种操作：
I C1 C2 K: 把C1与C2的路径上的所有点权值加上K
D C1 C2 K：把C1与C2的路径上的所有点权值减去K
Q C：查询节点编号为C的权值
裸裸的树剖
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 typedef long long LL; 10 11 #define N 50010 12 13 struct Node 14 { 15 int to,next; 16 }e[N<<1]; 17 18 int id,cnt; 19 int head[N]; 20 int num[N],siz[N],top[N],son[N]; 21 int dep[N],pos[N],rank1[N],fa[N]; 22 23 LL sum[N<<2],add[N<<2]; 24 25 char s[5]; 26 27 int n,m,q; 28 int u,v; 29 int al,ar,ask; 30 31 inline void init() 32 { 33 memset(son,-1,sizeof(son)); 34 memset(head,-1,sizeof(head)); 35 id=0; 36 cnt=0; 37 } 38 39 void link(int x,int y) 40 { 41 e[++cnt]=(Node){y,head[x]}; 42 head[x]=cnt; 43 } 44 45 void dfs(int x,int father,int d) 46 { 47 siz[x]=1; 48 dep[x]=d; 49 fa[x]=father; 50 for (int i=head[x];~i;i=e[i].next) 51 { 52 int t=e[i].to; 53 if (t!=fa[x]) 54 { 55 dfs(t,x,d+1); 56 siz[x]+=siz[t]; 57 if (son[x]==-1 || siz[x]>siz[son[x]]) 58 son[x]=t; 59 } 60 } 61 } 62 63 void dfs2(int x,int cha) 64 { 65 top[x]=cha; 66 pos[x]=++id; 67 rank1[pos[x]]=x; 68 if (son[x]==-1) 69 return ; 70 dfs2(son[x],cha); 71 for(int i=head[x];~i;i=e[i].next) 72 { 73 int t=e[i].to; 74 if(t!=son[x] && t!=fa[x]) 75 dfs2(t,t); 76 } 77 } 78 79 void pushup(int now) 80 { 81 sum[now]=max(sum[now<<1],sum[now<<1|1]); 82 } 83 84 void pushdown(int now,int m) 85 { 86 if (add[now]) 87 { 88 add[now<<1]+=add[now]; 89 add[now<<1|1]+=add[now]; 90 sum[now<<1]+=add[now]*(m-(m>>1)); 91 sum[now<<1|1]+=add[now]*(m>>1); 92 add[now]=0; 93 } 94 } 95 96 void build(int nowl,int nowr,int now) 97 { 98 add[now]=0; 99 if (nowl==nowr) 100 { 101 sum[now]=num[rank1[nowl]]; 102 return ; 103 } 104 int mid=(nowl+nowr)>>1; 105 build(nowl,mid,now<<1); 106 build(mid+1,nowr,now<<1|1); 107 pushup(now); 108 } 109 110 void update(int nowl,int nowr,int now,int L,int R,int d) 111 { 112 if (nowl>=L && nowr<=R) 113 { 114 add[now]+=d; 115 sum[now]+=d*(nowr-nowl+1); 116 return ; 117 } 118 pushdown(now,nowr-nowl+1); 119 int mid=nowl+nowr>>1; 120 if (L<=mid) update(nowl,mid,now<<1,L,R,d); 121 if (mid<R) update(mid+1,nowr,now<<1|1,L,R,d); 122 pushup(now); 123 } 124 125 int query(int nowl,int nowr,int now,int d) 126 { 127 int res(0); 128 if (nowl==nowr) 129 return sum[now]; 130 pushdown(now,nowr-nowl+1); 131 int mid=nowl+nowr>>1; 132 if (d<=mid) res=query(nowl,mid,now<<1,d); 133 else res=query(mid+1,nowr,now<<1|1,d); 134 pushup(now); 135 return res; 136 } 137 138 void work(int x,int y,int val) 139 { 140 while (top[x]!=top[y]) 141 { 142 if (dep[top[x]]<dep[top[y]]) 143 swap(x,y); 144 update(1,n,1,pos[top[x]],pos[x],val); 145 x=fa[top[x]]; 146 } 147 if (dep[x]>dep[y]) 148 swap(x,y); 149 update(1,n,1,pos[x],pos[y],val); 150 } 151 int main() 152 { 153 while (scanf("%d%d%d",&n,&m,&q)!=EOF && n+m+q) 154 { 155 init(); 156 for (int i=1;i<=n;i++) 157 scanf("%d",&num[i]); 158 for (int i=1;i<=m;i++) 159 { 160 scanf("%d%d",&u,&v); 161 link(u,v); 162 link(v,u); 163 } 164 dfs(1,0,0); 165 dfs2(1,1); 166 build(1,n,1); 167 while (q--) 168 { 169 scanf("%s",s); 170 if (s[0]=='I') 171 { 172 scanf("%d%d%d",&al,&ar,&ask); 173 work(al,ar,ask); 174 } 175 else if (s[0]=='D') 176 { 177 scanf("%d%d%d",&al,&ar,&ask); 178 work(al,ar,-ask); 179 } 180 else 181 { 182 scanf("%d",&ask); 183 printf("%d ",query(1,n,1,pos[ask])); 184 } 185 } 186 } 187 return 0; 188 }