P2590 树的统计

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<algorithm>

  4 using namespace std;

  5 const int N = 3e4+10;

  6 string opt;

  7 int n,m,x,y,tot,num;

  8 int dfn[N],son[N],head[N],size[N],fa[N];

  9 int dep[N],top[N],w[N],a[N];

 10 struct node{

 11     int to;

 12     int net;

 13 }e[N*2];

 14 void add_(int x,int y){//加边操作

 15     tot++;

 16     e[tot].to = y;

 17     e[tot].net = head[x];

 18     head[x] = tot;

 19 }

 20 void get_tree(int x){//第一遍dfs求每个点的重儿子

 21     dep[x] = dep[fa[x]] + 1;

 22     size[x] = 1;

 23     for(int i = head[x]; i; i = e[i].net){

 24         int to = e[i].to;

 25         if(to == fa[x]) continue;

 26         fa[to] = x;

 27         get_tree(to);

 28         size[x] += size[to];

 29         if(size[to] > size[son[x]]) son[x] = to;

 30     }

 31 }

 32 void dfs(int x,int topp){//第二遍dfs求每个点的top

 33     top[x] = topp;

 34     dfn[x] = ++num;//每个点的dfs序，方便之后建线段树

 35     w[dfn[x]] = a[x];

 36     if(son[x]) dfs(son[x],topp);

 37     for(int i = head[x]; i; i = e[i].net){

 38         int to = e[i].to;

 39         if(to == fa[x] || to == son[x]) continue;

 40         dfs(to,to);

 41     }

 42 }

 43 struct tree{//线段树常规操作

 44     #define l(o) tr[o].lc

 45     #define r(o) tr[o].rc

 46     #define sum(o) tr[o].sum

 47     #define add(o) tr[o].add

 48     #define maxn(o) tr[o].maxn

 49     struct qxh{

 50         int lc,rc;

 51         int maxn,add,sum;

 52     }tr[N<<2];

 53     void up(int o){

 54         sum(o) = sum(o*2) + sum(o*2+1);

 55         maxn(o) = max(maxn(o*2) , maxn(o*2+1));

 56     }

 57     void build(int o, int L,int R){//按每个点的dfs序建树

 58         l(o) = L; r(o) = R;

 59         if(L == R){

 60             sum(o) = maxn(o) = w[L];

 61             return ;

 62         }

 63         int mid = (L + R) / 2;

 64         build(o*2,L,mid);

 65         build(o*2+1,mid+1,R);

 66         up(o);

 67     }

 68     void chenge(int o,int L,int R,int val){//单点修改变区间修改

 69         if(L <= l(o) && R >= r(o)){

 70             sum(o) = val;

 71             maxn(o) = val;

 72             return ;

 73         }

 74         int mid = (l(o) + r(o)) / 2;

 75         if(L <= mid) chenge(o*2,L,R,val);

 76         if(R > mid) chenge(o*2+1,L,R,val);

 77         up(o);

 78     }

 79     int ask_sum(int o,int L,int R){//询问区间的和

 80         int ans = 0;

 81         if(L <= l(o) && R >= r(o)){

 82             return sum(o);

 83         }

 84         int mid = (l(o) + r(o)) / 2;

 85         if(L <= mid) ans += ask_sum(o*2,L,R);

 86         if(R > mid) ans += ask_sum(o*2+1,L,R);

 87         return ans;

 88     }

 89     int ask_max(int o,int L,int R){//区间最大值

 90         int ans = -2147483647; //一定要初值为负数，否则就会炸掉

 91         if(L <= l(o) && R >= r(o)){

 92             return maxn(o);

 93         }

 94         int mid = (l(o) + r(o)) / 2;

 95         if(L <= mid) ans = max(ans,ask_max(o*2,L,R));

 96         if(R > mid) ans = max(ans,ask_max(o*2+1,L,R));

 97         return ans;

 98     }

 99 }tree;

100 int query_sum(int x,int y){//求树上路径的和

101     int ans = 0;

102     while(top[x] != top[y]){//边跳边修改

103         if(dep[top[x]] < dep[top[y]]) swap(x,y);

104         ans += tree.ask_sum(1, dfn[top[x]] , dfn[x]);

105         x = fa[top[x]];

106     }

107     if(dep[x] > dep[y]) swap(x,y);//使dfn[x] ~dfn[y]这一段区间的序号保持有序

108     ans += tree.ask_sum(1,dfn[x],dfn[y]);

109     return ans;

110 }

111 int query_max(int x,int y){//求树上路径和，同上

112     int ans = -2147483647;//赋初值。。。。

113     while(top[x] != top[y]){

114         if(dep[top[x]] < dep[top[y]]) swap(x,y);

115         ans = max(ans,tree.ask_max(1,dfn[top[x]],dfn[x]));

116         x = fa[top[x]];

117     }

118     if(dep[x] > dep[y]) swap(x,y);

119     ans = max(ans,tree.ask_max(1,dfn[x],dfn[y]));

120     return ans;

121 }

122 int main(){

123     scanf("%d",&n);

124     for(int i = 1; i <= n-1; i++){

125         scanf("%d%d",&x,&y);

126         add_(x,y);//建双向边

127         add_(y,x);

128     }

129     for(int i = 1; i <= n; i++) scanf("%d",&a[i]);

130     get_tree(1);//预处理

131     dfs(1,1);

132     tree.build(1,1,n);

133     scanf("%d",&m);

134     while(m--){

135         cin>>opt;

136         scanf("%d%d",&x,&y);

137         if(opt == "CHANGE"){

138             tree.chenge(1,dfn[x],dfn[x],y);

139         }

140         if(opt == "QMAX"){

141             printf("%d\n",query_max(x,y));

142         }

143         if(opt == "QSUM"){

144             printf("%d\n",query_sum(x,y));

145         }

146     }

147     return 0;

148 }