题目传送门
跟板子差不多
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 int n,head[30001],tot,w[30001],rk[30001],p; 8 long long ans; 9 struct kkk { 10 int to,next; 11 }e[60001]; 12 struct poufen { 13 int deep,f,si,son,top,id; 14 }q[30001]; 15 struct xianduanshu { 16 int l,r,v,mm,lazy; 17 }a[120001]; 18 19 inline void add(int x,int y) { 20 e[++tot].to = y; 21 e[tot].next = head[x]; 22 head[x] = tot; 23 } 24 25 inline void dfs1(int rt,int fa,int d) { 26 q[rt].deep = d; 27 q[rt].f = fa; 28 q[rt].si = 1; 29 q[rt].son = 0; 30 for(int i = head[rt];i; i = e[i].next) { 31 int u = e[i].to; 32 if(u == fa) continue; 33 dfs1(u,rt,d + 1); 34 q[rt].si += q[u].si; 35 if(q[q[rt].son].si < q[u].si) q[rt].son = u; 36 } 37 } 38 39 inline void dfs2(int rt,int topf) { 40 q[rt].top = topf; 41 q[rt].id = ++tot; 42 rk[tot] = rt; 43 if(q[rt].son == 0) return ; 44 dfs2(q[rt].son,topf); 45 for(int i = head[rt];i; i = e[i].next) { 46 int u = e[i].to; 47 if(u == q[rt].son || u == q[rt].f) continue; 48 dfs2(u,u); 49 } 50 } 51 52 inline int max(int uu,int oo) { 53 if(uu > oo) return uu; 54 return oo; 55 } 56 57 inline long long max1(long long uu,int oo) { 58 if(uu > oo) return uu; 59 return oo; 60 } 61 62 inline void build(int rt,int ll,int rr) { 63 a[rt].l = ll; 64 a[rt].r = rr; 65 if(ll == rr) { 66 a[rt].v = w[rk[ll]]; 67 a[rt].mm = a[rt].v; 68 return ; 69 } 70 int mid = (ll + rr) >> 1; 71 build(rt * 2,ll,mid); 72 build(rt * 2 + 1,mid + 1,rr); 73 a[rt].v = a[rt*2].v + a[rt*2+1].v; 74 a[rt].mm = max(a[rt*2].mm,a[rt*2+1].mm); 75 } 76 77 inline void change(int rt,int l,int len) { 78 if(a[rt].l == l && a[rt].r == l) { 79 a[rt].v = len; 80 a[rt].mm = len; 81 return ; 82 } 83 int mid = (a[rt].l + a[rt].r) >> 1; 84 if(l <= mid) change(rt * 2,l,len); 85 else change(rt * 2 + 1,l,len); 86 a[rt].v = a[rt*2].v + a[rt*2+1].v; 87 a[rt].mm = max(a[rt*2].mm,a[rt*2+1].mm); 88 } 89 90 inline void find_max(int rt,int L,int R) { 91 if(a[rt].l >= L && a[rt].r <= R) { 92 ans = max1(ans,a[rt].mm); 93 return ; 94 } 95 int mid = (a[rt].l + a[rt].r) >> 1; 96 if(L <= mid) find_max(rt * 2,L,R); 97 if(R > mid) find_max(rt*2+1,L,R); 98 } 99 100 inline void treefind(int x,int y) { 101 int tx = q[x].top; 102 int ty = q[y].top; 103 while(ty != tx) { 104 if(q[tx].deep >= q[ty].deep) { 105 find_max(1,q[tx].id,q[x].id); 106 x = q[tx].f;tx = q[x].top; 107 } 108 else { 109 find_max(1,q[ty].id,q[y].id); 110 y = q[ty].f;ty = q[y].top; 111 } 112 } 113 if(q[x].deep >= q[y].deep) 114 find_max(1,q[y].id,q[x].id); 115 else 116 find_max(1,q[x].id,q[y].id); 117 } 118 119 inline int qiuhe(int rt,int L,int R) { 120 int pp = 0; 121 if(a[rt].l >= L && a[rt].r <= R) 122 return a[rt].v; 123 int mid = (a[rt].l + a[rt].r) >> 1; 124 if(L <= mid) pp += qiuhe(rt * 2,L,R); 125 if(R > mid) pp += qiuhe(rt * 2 + 1,L,R); 126 return pp; 127 } 128 129 inline int treesum(int x,int y) { 130 int tx = q[x].top; 131 int ty = q[y].top; 132 int daan = 0; 133 while(ty != tx) { 134 if(q[tx].deep > q[ty].deep) { 135 daan += qiuhe(1,q[tx].id,q[x].id); 136 x = q[tx].f;tx = q[x].top; 137 } 138 else { 139 daan += qiuhe(1,q[ty].id,q[y].id); 140 y = q[ty].f;ty = q[y].top; 141 } 142 } 143 if(q[x].deep >= q[y].deep) 144 daan += qiuhe(1,q[y].id,q[x].id); 145 else 146 daan += qiuhe(1,q[x].id,q[y].id); 147 return daan; 148 } 149 // 150 //inline void PPPP(int r) { 151 // if(a[r].l == a[r].r) { 152 // printf("%d ",a[r].mm); 153 // return ; 154 // } 155 // PPPP(r*2); 156 // PPPP(r*2+1); 157 //} 158 159 int main() { 160 scanf("%d",&n); 161 for(int i = 1;i <= n - 1; i++) { 162 int x,y; 163 scanf("%d%d",&x,&y); 164 add(x,y); 165 add(y,x); 166 } 167 for(int i = 1;i <= n; i++) 168 scanf("%d",&w[i]); 169 dfs1(1,0,1); 170 tot = 0; 171 dfs2(1,1); 172 build(1,1,n); 173 scanf("%d",&p); 174 for(int i = 1;i <= p; i++) { 175 string r; 176 cin >> r; 177 if(r == "CHANGE") { 178 int x,y; 179 scanf("%d%d",&x,&y); 180 change(1,q[x].id,y); 181 //PPPP(1); 182 } 183 if(r == "QMAX") { 184 int x,y; 185 ans = -10000000000; 186 scanf("%d%d",&x,&y); 187 treefind(x,y); 188 printf("%lld ",ans); 189 } 190 if(r == "QSUM") { 191 int x,y; 192 scanf("%d%d",&x,&y); 193 printf("%d ",treesum(x,y)); 194 } 195 } 196 return 0; 197 }