题意：给一棵树，并给定各个点权的值，然后有3种操作：
I C1 C2 K: 把C1与C2的路径上的所有点权值加上K
D C1 C2 K：把C1与C2的路径上的所有点权值减去K
Q C：查询节点编号为C的权值
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 #define N 50010 8 #define ls o<<1 9 #define rs o<<1|1 10 #define define_m int m=(l+r)>>1 11 #define ll long long 12 int n , m , q , first[N] , k; 13 14 struct Edge{ 15 int y , next; 16 Edge(){} 17 Edge(int y , int next):y(y),next(next){} 18 }e[N<<1]; 19 20 void add_edge(int x , int y) 21 { 22 e[k] = Edge(y , first[x]); 23 first[x] = k++; 24 } 25 26 int sz[N] , fa[N] , son[N] , top[N] , dep[N] , id[N] , number; 27 void dfs(int u , int f , int d) 28 { 29 fa[u] = f; 30 sz[u] = 1 , dep[u] = d , son[u] =0; 31 int maxn = 0; 32 for(int i=first[u] ; ~i ; i=e[i].next){ 33 int v= e[i].y; 34 if(v == f) continue; 35 dfs(v , u , d+1); 36 sz[u] += sz[v]; 37 if(sz[v]>maxn) son[u] = v , maxn=sz[v]; 38 } 39 } 40 41 void dfs1(int u , int f , int head) 42 { 43 top[u] = head; 44 if(son[u]){ 45 id[son[u]] = ++number; 46 dfs1(son[u] , u , head); 47 } 48 for(int i=first[u] ; ~i ; i=e[i].next){ 49 int v = e[i].y; 50 if(v == f || v == son[u]) continue; 51 id[v] = ++number; 52 dfs1(v , u , v); 53 } 54 } 55 56 int val[N] , add[N<<2] , siz[N<<2]; 57 ll sum[N<<2]; 58 59 void push_up(int o){sum[o] = sum[ls]+sum[rs];} 60 61 void push_down(int o) 62 { 63 if(add[o]){ 64 add[ls] += add[o] , add[rs] += add[o]; 65 sum[ls] += (ll)add[o]*siz[ls] , sum[rs] += (ll)add[o]*siz[rs]; 66 add[o] = 0; 67 } 68 } 69 70 void build(int o , int l , int r) 71 { 72 add[o] = 0 , siz[o] = r-l+1; 73 if(l==r){ 74 sum[o] = (ll)val[l]; 75 return ; 76 } 77 define_m; 78 build(ls , l , m); 79 build(rs , m+1 , r); 80 push_up(o); 81 } 82 83 void update(int o , int l , int r , int s , int t , int v) 84 { 85 if(l>=s && r<=t){ 86 sum[o] += (ll)siz[o]*v; 87 add[o] += v; 88 return ; 89 } 90 define_m; 91 push_down(o); 92 if(m>=s) update(ls , l , m , s , t , v); 93 if(m<t) update(rs , m+1 , r , s , t , v); 94 push_up(o); 95 } 96 97 ll query(int o , int l , int r , int p) 98 { 99 if(l==r && l==p) return sum[o]; 100 push_down(o); 101 define_m; 102 if(m>=p) return query(ls , l , m, p); 103 else return query(rs , m+1 , r , p); 104 } 105 106 void updatePath(int u , int v , int change) 107 { 108 int top1 = top[u] , top2 = top[v]; 109 while(top1!=top2){ 110 if(dep[top1]<dep[top2]){ 111 swap(top1 , top2); 112 swap(u , v); 113 } 114 update(1 , 1 , n , id[top1] , id[u] , change); 115 u = fa[top1]; 116 top1 = top[u]; 117 } 118 119 if(dep[u]<dep[v]) swap(u , v); 120 update(1 , 1 , n , id[v] , id[u] , change); 121 122 } 123 124 char str[4]; 125 126 int main() 127 { 128 // freopen("in.txt" , "r" , stdin); 129 while(~scanf("%d%d%d" ,&n , &m , &q)) 130 { 131 for(int i=1 ; i<=n ; i++) scanf("%d" , val+i); 132 memset(first , -1 , sizeof(first)); 133 k = 0; 134 while(m--){ 135 int u , v; 136 scanf("%d%d" , &u , &v); 137 add_edge(u,v); 138 add_edge(v,u); 139 } 140 number = 0; 141 dfs(1 , 0 , 1); 142 id[1] = ++number; 143 dfs1(1 , 0 , 1); 144 // for(int i=1 ; i<=n ; i++) cout<<i<<" "<<son[i]<<" "<<id[i]<<endl; 145 int tmp[N]; 146 for(int i=1 ; i<=n ; i++) tmp[i]=val[i]; 147 for(int i=1 ; i<=n ; i++) val[id[i]] = tmp[i]; 148 build(1 , 1 , n); 149 for(int i=0 ; i<q ; i++){ 150 int s , t , v; 151 scanf("%s" , str); 152 if(str[0] == 'Q'){ 153 scanf("%d" , &v); 154 ll ans = query(1 , 1 , n , id[v]); 155 printf("%d " , (int)ans); 156 }else if(str[0]=='I'){ 157 scanf("%d%d%d" , &s , &t , &v); 158 updatePath(s , t , v); 159 }else{ 160 scanf("%d%d%d" , &s , &t , &v); 161 updatePath(s , t , -v); 162 } 163 } 164 } 165 return 0; 166 }