P2590 [ZJOI2008]树的统计

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #define Rint register int
  7 #define mem(a,b) memset(a,(b),sizeof(a))
  8 #define Temp template<typename T>
  9 using namespace std;
 10 typedef long long LL;
 11 const int maxn=200000+10;
 12 int n,m;
 13 //见题意
 14 int w[maxn],wt[maxn];
 15 //链式前向星数组，w[]、wt[]初始点权数组
 16 int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
 17 //son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
 18 //查询答案
 19 struct node
 20 {
 21     int v,nxt;
 22 }G[maxn<<2]; int head[maxn]; int num;
 23 struct tre
 24 {
 25     int l,r,lazy,sum,mx;
 26 }tree[maxn<<2];
 27 void add(int u,int v)
 28 {
 29     G[++num].v=v;G[num].nxt=head[u];head[u]=num;
 30     G[++num].v=u;G[num].nxt=head[v];head[v]=num;
 31 }
 32 
 33 void build(int l,int r,int root){
 34     tree[root].l=l;tree[root].r=r;
 35     tree[root].sum=tree[root].lazy=0;
 36     if(l==r){
 37         tree[root].sum=wt[l];
 38         tree[root].mx=wt[l];
 39         return;
 40     }
 41     int mid=l+r>>1;
 42     build(l,mid,root<<1);
 43     build(mid+1,r,root<<1|1);
 44     tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
 45     tree[root].mx=max(tree[root<<1].mx,tree[root<<1|1].mx);
 46 }
 47 
 48 tre query(int l,int r,int root){
 49     int L=tree[root].l;int R=tree[root].r;
 50     if(l<=L&&R<=r){
 51         return tree[root];
 52     }
 53     int mid=L+R>>1;
 54     tre ans;
 55     int flag=0;
 56     if(l<=mid) ans=query(l,r,root<<1),flag=1;
 57     if(r>mid){
 58         if(!flag) ans=query(l,r,root<<1|1);
 59         else{
 60             tre tmp=query(l,r,root<<1|1);
 61             ans.mx=max(ans.mx,tmp.mx);
 62             ans.sum+=tmp.sum;
 63         }
 64     }
 65     return ans;
 66 }
 67 void update(int l,int r,int val,int root){
 68     int L=tree[root].l;int R=tree[root].r;
 69     if(l<=L&&R<=r){
 70         tree[root].sum=val;
 71         tree[root].mx=val;
 72     }
 73     else{
 74         int mid=L+R>>1;
 75         if(l<=mid)update(l,r,val,root<<1);
 76         if(r>mid) update(l,r,val,root<<1|1);
 77         tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
 78         tree[root].mx=max(tree[root<<1].mx,tree[root<<1|1].mx);
 79     }
 80 }
 81 tre qRange(int x,int y){
 82     tre ans;
 83     int flag=0;
 84     while(top[x]!=top[y]){//当两个点不在同一条链上
 85         if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
 86         if(!flag)
 87             ans=query(id[top[x]],id[x],1),flag=1;//ans加上x点到x所在链顶端 这一段区间的点权和
 88         else{
 89             tre tmp;
 90             tmp=query(id[top[x]],id[x],1);
 91             ans.sum+=tmp.sum;
 92             ans.mx=max(ans.mx,tmp.mx);
 93         }
 94         x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
 95     }
 96     //直到两个点处于一条链上
 97     if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
 98     tre tmp=query(id[x],id[y],1);//这时再加上此时两个点的区间和即可
 99     if(!flag) return tmp;
100     else{
101         ans.sum+=tmp.sum;
102         ans.mx=max(ans.mx,tmp.mx);
103     }
104     return ans;
105 }
106 
107 
108 void dfs1(int u,int f,int deep){//x当前节点，f父亲，deep深度
109     dep[u]=deep;//标记每个点的深度
110     fa[u]=f;//标记每个点的父亲
111     siz[u]=1;//标记每个非叶子节点的子树大小
112     int maxson=-1;//记录重儿子的儿子数
113     for(int i=head[u];i!=-1;i=G[i].nxt){
114         int v=G[i].v;
115         if(v==f)continue;//若为父亲则continue
116         dfs1(v,u,deep+1);//dfs其儿子
117         siz[u]+=siz[v];//把它的儿子数加到它身上
118         if(siz[v]>maxson)son[u]=v,maxson=siz[v];//标记每个非叶子节点的重儿子编号
119     }
120 }
121 
122 void dfs2(int u,int topf){//x当前节点，topf当前链的最顶端的节点
123     id[u]=++cnt;//标记每个点的新编号
124     wt[cnt]=w[u];//把每个点的初始值赋到新编号上来
125     top[u]=topf;//这个点所在链的顶端
126     if(!son[u])return;//如果没有儿子则返回
127     dfs2(son[u],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
128     for(int i=head[u];i!=-1;i=G[i].nxt){
129         int v=G[i].v;
130         if(v==fa[u]||v==son[u])continue;
131         dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
132     }
133 }
134 void init()
135 {
136     memset(head,-1,sizeof(head));
137     num=-1;
138 }
139 int main(){
140     init();
141     int n;
142     scanf("%d",&n);
143     for(int i=1;i<n;i++){
144         int u,v;
145         scanf("%d%d",&u,&v);
146         add(u,v);
147     }
148     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
149     dfs1(1,0,1); dfs2(1,1);
150     build(1,n,1);
151     int T;
152     scanf("%d",&T);
153     while(T--){
154         string tmp1;
155         int tmp2,tmp3;
156         cin>>tmp1>>tmp2>>tmp3;
157         if(tmp1[0]==‘C‘){
158             update(id[tmp2],id[tmp2],tmp3,1);
159         }
160         else if(tmp1[1]==‘M‘){
161             tre ans=qRange(tmp2,tmp3);
162             printf("%d\n",ans.mx);
163         }
164         else{
165             tre ans=qRange(tmp2,tmp3);
166             printf("%d\n",ans.sum);
167         }
168     }
169     return 0;
170 }