题目大意：给出一棵树，每个点有一个权值，要求三种操作：1.修改某个点的权值，2.询问x到y路径上各点的权值最大值，3.询问x到y路径上各点的权值之和。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define N 30010 7 #define ls o<<1 8 #define rs o<<1|1 9 #define define_m int m=(l+r)>>1 10 11 int first[N] , k; 12 struct Edge{ 13 int y , next; 14 }e[N<<1]; 15 16 void add_edge(int x , int y) 17 { 18 e[k].y = y , e[k].next = first[x]; 19 first[x] = k++; 20 } 21 22 int sz[N] , dep[N] , fa[N] , son[N] , top[N] , id[N] , num; 23 void dfs(int u , int f , int d) 24 { 25 fa[u] = f , sz[u] = 1 , dep[u]= d , son[u]=0; 26 int mx = 0; 27 for(int i=first[u] ; ~i ; i=e[i].next){ 28 int v = e[i].y; 29 if(v == f) continue; 30 dfs(v , u , d+1); 31 sz[u]+=sz[v]; 32 if(sz[v]>mx) mx=sz[v] , son[u]=v; 33 } 34 } 35 36 void dfs1(int u , int f , int head) 37 { 38 top[u]=head , id[u]=++num; 39 if(son[u]) dfs1(son[u] , u , head); 40 for(int i=first[u] ; ~i ; i=e[i].next){ 41 int v = e[i].y; 42 if(v == f || v == son[u]) continue; 43 dfs1(v , u , v); 44 } 45 } 46 47 int sum[N<<2] , mx[N<<2] , val[N]; 48 void push_up(int o) 49 { 50 sum[o] = sum[ls]+sum[rs]; 51 mx[o] = max(mx[ls] , mx[rs]); 52 } 53 54 void build(int o , int l , int r) 55 { 56 if(l==r){ 57 sum[o]=mx[o]=val[l]; 58 return ; 59 } 60 define_m; 61 build(ls , l , m); 62 build(rs , m+1 , r); 63 push_up(o); 64 } 65 66 void update(int o , int l , int r , int p , int v) 67 { 68 if(l==r){ 69 sum[o]=mx[o]=v; 70 return; 71 } 72 define_m; 73 if(m>=p) update(ls , l , m , p , v); 74 else update(rs , m+1 , r , p , v); 75 push_up(o); 76 } 77 78 int qSum(int o , int l , int r , int s , int t) 79 { 80 if(l>=s && r<=t) return sum[o]; 81 define_m; 82 int res = 0; 83 if(m>=s) res+=qSum(ls , l , m , s , t); 84 if(m<t) res+=qSum(rs , m+1 , r , s , t); 85 return res; 86 } 87 88 int qMax(int o , int l , int r , int s , int t) 89 { 90 if(l>=s && r<=t) return mx[o]; 91 define_m; 92 int res = -1e9; 93 if(m>=s) res = max(res , qMax(ls , l , m , s , t)); 94 if(m<t) res = max(res , qMax(rs , m+1 , r , s , t)); 95 return res; 96 } 97 98 int calPath(int u , int v , int flag) 99 { 100 int top1 = top[u] , top2 = top[v] , ret=-1e9; 101 if(flag) ret=0; 102 while(top1!=top2){ 103 if(dep[top1]<dep[top2]){ 104 swap(top1 , top2); 105 swap(u , v); 106 } 107 if(flag) ret+=qSum(1 , 1 , num , id[top1] , id[u]); 108 else ret=max(ret , qMax(1,1,num,id[top1] , id[u])); 109 u = fa[top1]; 110 top1 = top[u]; 111 } 112 if(dep[u]<dep[v]) swap(u,v); 113 if(flag) ret+=qSum(1,1,num,id[v],id[u]); 114 else ret=max(ret , qMax(1,1,num,id[v],id[u])); 115 return ret; 116 } 117 char str[8]; 118 int main() 119 { 120 //freopen("in.txt" , "r" , stdin); 121 int n , x , y , q; 122 while(scanf("%d" , &n)!=EOF) 123 { 124 memset(first , -1 , sizeof(first)); 125 k = 0; 126 for(int i=1 ; i<n ; i++){ 127 scanf("%d%d" , &x , &y); 128 add_edge(x , y); 129 add_edge(y , x); 130 } 131 dfs(1 , 0 , 1); 132 num = 0; 133 dfs1(1 , 0 , 1); 134 int tmp[N]; 135 for(int i=1 ; i<=n ; i++) scanf("%d" , val+i) , tmp[i]=val[i]; 136 for(int i=1 ; i<=n ; i++) val[id[i]]=tmp[i]; 137 build(1 , 1 , num); 138 // for(int i=1 ; i<=7 ; i++) cout<<i<<" "<<mx[i]<<" "<<sum[i]<<endl; 139 scanf("%d" , &q); 140 while(q--){ 141 scanf("%s%d%d", str , &x , &y); 142 if(str[0]=='C'){ 143 update(1 , 1 , num , id[x] , y); 144 } 145 else if(str[1]=='M'){ 146 int ret = calPath(x , y , 0); 147 printf("%d " , ret); 148 }else{ 149 int ret = calPath(x , y , 1); 150 printf("%d " , ret); 151 } 152 } 153 } 154 return 0; 155 }