P2590 [ZJOI2008]树的统计

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdbool.h>
  5 #include <stdlib.h>
  6 #include <string>
  7 #include <string.h>
  8 #include <stack>
  9 #include <queue>
 10 #include <set>
 11 #include <map>
 12 #include <math.h>
 13 
 14 #define INF 0x3f3f3f3f
 15 #define LL long long
 16 using namespace std;
 17 
 18 const int maxn = 300100;
 19 
 20 struct Edge{
 21     int to,next;
 22 }edge[maxn*4];
 23 
 24 int head[maxn],tot;
 25 
 26 void add_edge(int u,int v){
 27     edge[++tot] = Edge{v,head[u]};
 28     head[u] = tot;
 29 }
 30 
 31 int v[maxn];
 32 int fa[maxn];
 33 int siz[maxn];
 34 int dep[maxn];
 35 int son[maxn];
 36 
 37 void dfs1(int u,int f){
 38     fa[u] = f;
 39     dep[u] = dep[f] + 1;
 40     siz[u] = 1;
 41     int maxsize = -1;
 42     for (int i=head[u];~i;i=edge[i].next){
 43         int v = edge[i].to;
 44         if (v == f){
 45             continue;
 46         }
 47         dfs1(v,u);
 48         siz[u] += siz[v];
 49         if (siz[v] > maxsize){
 50             maxsize = siz[v];
 51             son[u] = v;
 52         }
 53     }
 54 }
 55 
 56 
 57 int tim;
 58 int dfn[maxn];
 59 int top[maxn];
 60 int w[maxn];
 61 
 62 void dfs2(int u,int t){
 63     dfn[u] = ++tim;
 64     top[u] = t;
 65     w[tim] = v[u];
 66     if (!son[u]){
 67         return ;
 68     }
 69     dfs2(son[u],t);
 70     for (int i=head[u];~i;i=edge[i].next){
 71         int v = edge[i].to;
 72         if (v == fa[u] || v == son[u]){
 73             continue;
 74         }
 75         dfs2(v,v);
 76     }
 77 }
 78 
 79 
 80 struct segment_tree{
 81     int l,r;
 82     LL val;
 83     LL maxval;
 84     int lazy;
 85 }tree[maxn*4];
 86 
 87 void pushup(int nod){
 88     tree[nod].val = (tree[nod<<1].val + tree[(nod<<1)+1].val);
 89     tree[nod].maxval = max(tree[nod<<1].maxval,tree[(nod<<1)+1].maxval);
 90 }
 91 
 92 void build (int l,int r,int nod){
 93     tree[nod].l = l;
 94     tree[nod].r = r;
 95     if (l == r){
 96         tree[nod].lazy = 0;
 97         tree[nod].val = w[l];
 98         tree[nod].maxval = w[l];
 99         return ;
100     }
101     int mid = (l + r) >> 1;
102     build(l,mid,nod<<1);
103     build(mid+1,r,(nod<<1)+1);
104     pushup(nod);
105 }
106 
107 void modify(int k,int value,int nod=1){
108     if (tree[nod].l == k && tree[nod].r == k){
109         tree[nod].val = tree[nod].maxval = value;
110         return ;
111     }
112     int mid = (tree[nod].l + tree[nod].r) >> 1;
113     if (k <= mid){
114         modify(k,value,nod<<1);
115     }
116     else
117         modify(k,value,(nod<<1)+1);
118     pushup(nod);
119 }
120 
121 
122 LL query(int x,int y,int k){
123     int l = tree[k].l,r = tree[k].r;
124     if (x <= l && y >= r){
125         return tree[k].val;
126     }
127     int mid = (l + r) >> 1;
128     LL sum = 0;
129     if (x <= mid){
130         sum += query(x,y,k<<1);
131     }
132     if (y > mid){
133         sum += query(x,y,(k<<1)+1);
134     }
135     return sum;
136 }
137 
138 LL query2(int x,int y,int k){
139     int l = tree[k].l,r = tree[k].r;
140     if (x <= l && y >= r){
141         return tree[k].maxval;
142     }
143     int mid = (l + r) >> 1;
144     LL sum = -INF;
145     if (x <= mid){
146         sum = max(sum,query2(x,y,k<<1));
147     }
148     if (y > mid){
149         sum = max(query2(x,y,(k<<1)+1),sum);
150     }
151     return sum;
152 }
153 
154 LL query_max(int x,int y){
155     LL ret = -INF;
156     while (top[x] != top[y]){
157         if (dep[top[x]] < dep[top[y]])
158             swap(x,y);
159         ret = max(ret,query2(dfn[top[x]],dfn[x],1));
160         x = fa[top[x]];
161     }
162     if (dep[x] > dep[y])
163         swap(x,y);
164     ret = max(ret,query2(dfn[x],dfn[y],1));
165     return ret;
166 }
167 
168 LL query_sum(int x,int y){
169     LL ret = 0;
170     while (top[x] != top[y]){
171         if (dep[top[x]] < dep[top[y]])
172             swap(x,y);
173         ret += query(dfn[top[x]],dfn[x],1);
174         x = fa[top[x]];
175     }
176     if (dep[x] > dep[y])
177         swap(x,y);
178     ret += query(dfn[x],dfn[y],1);
179     return ret;
180 }
181 
182 int main(){
183     int n;
184     scanf("%d",&n);
185     memset(head,-1, sizeof(head));
186     for (int i=1;i<=n-1;i++){
187         int x,y;
188         scanf("%d%d",&x,&y);
189         add_edge(x,y);
190         add_edge(y,x);
191     }
192     for (int i=1;i<=n;i++){
193         scanf("%d",&v[i]);
194     }
195     dfs1(1,1);
196     dfs2(1,1);
197     build(1,n,1);
198     int T;
199     scanf("%d",&T);
200     while (T--){
201         char s[10];
202         int x,y,z;
203         scanf("%s",s);
204         if (strcmp(s,"CHANGE") == 0){
205             scanf("%d%d",&x,&z);
206             modify(dfn[x],z);
207         }
208         else if (strcmp(s,"QMAX") == 0) {
209             scanf("%d%d",&x,&y);
210             printf("%lld\n",query_max(x,y));
211         }
212         else if (strcmp(s,"QSUM") == 0){
213             scanf("%d%d",&x,&y);
214             printf("%lld\n",query_sum(x,y));
215         }
216     }
217     return 0;
218 }