bzoj1036:[ZJOI2008]树的统计Count

树的统计CountTime Limit: 10 Sec Memory Limit: 162 MB
Submit: 9540 Solved: 3854
[Submit][Status][Discuss]

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身

Input

输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

HINT

Source

树的分治

[Submit][Status][Discuss]

题解：裸的树链剖分，单点修改，区间查询。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue> 
  9 using namespace std;
 10 const int maxn=30010;
 11 const int inf=1e9;
 12 int dep[maxn],siz[maxn];
 13 int fa[maxn],id[maxn],son[maxn],val[maxn],top[maxn];
 14 int num;
 15 vector<int> to[maxn];
 16 int N,M;
 17 //第一遍 dfs 处理出 dep，siz，fa，son， 
 18 void dfs1(int rt,int fath,int deep){
 19     dep[rt]=deep; siz[rt]=1; son[rt]=0; fa[rt]=fath;
 20     for(int i=0;i<to[rt].size();i++){
 21         int y=to[rt][i];
 22         if(y!=fa[rt]){
 23             dfs1(y,rt,deep+1);
 24             siz[rt]+=siz[y];
 25             if(siz[son[rt]]<siz[y]){
 26                 son[rt]=y;
 27             }
 28         }
 29     }
 30 }
 31 //第二次 dfs 处理处 top[rt] 表示rt所在的重路径中深度最小的节点 
 32  
 33 void dfs2(int rt,int tp){
 34     top[rt]=tp;
 35     id[rt]=++num;//记录每个节点的编号 
 36     if(son[rt]!=0) dfs2(son[rt],tp);//有孩子 
 37     for(int i=0;i<to[rt].size();i++){
 38         int y=to[rt][i];
 39         if(y!=fa[rt]&&y!=son[rt]){
 40             dfs2(y,y);//重新开始找以y为起点的重路经 
 41         }
 42     }
 43 }
 44 
 45 struct Tree{
 46     int l,r,val,sum;
 47 }tree[maxn*8];
 48 void build(int rt,int l,int r){
 49     tree[rt].l=l; tree[rt].r=r;
 50     if(l==r){
 51         tree[rt].val=val[l];
 52         tree[rt].sum=val[l];
 53         return ;
 54     }
 55     int mid=(l+r)>>1;
 56     build(rt*2,l,mid);
 57     build(rt*2+1,mid+1,r);
 58     tree[rt].val=max(tree[rt*2].val,tree[rt*2+1].val);
 59     tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
 60 }
 61 inline void update(int rt,int v,int val){
 62     if(tree[rt].l==tree[rt].r){
 63         tree[rt].val=val;
 64         tree[rt].sum=val;
 65         return ;
 66     }
 67     int mid=(tree[rt].l+tree[rt].r)>>1;
 68     if(v<=mid) update(rt*2,v,val);
 69     else update(rt*2+1,v,val);
 70     tree[rt].val=max(tree[rt*2].val,tree[rt*2+1].val);
 71     tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
 72 }
 73 inline int queryMAX(int rt,int l,int r){
 74     if(l<=tree[rt].l&&tree[rt].r<=r){
 75         return tree[rt].val;
 76     }
 77     int mid=(tree[rt].l+tree[rt].r)>>1;
 78     int ans=-inf;
 79     if(l<=mid) ans=max(ans,queryMAX(rt*2,l,r));
 80     if(mid+1<=r) ans=max(ans,queryMAX(rt*2+1,l,r));
 81     return ans;
 82 }
 83 inline int querySUM(int rt,int l,int r){
 84     if(l<=tree[rt].l&&tree[rt].r<=r){
 85         return tree[rt].sum;
 86     }
 87     int mid=(tree[rt].l+tree[rt].r)>>1;
 88     int ans=0;
 89     if(l<=mid) ans+=querySUM(rt*2,l,r);
 90     if(mid+1<=r) ans+=querySUM(rt*2+1,l,r);
 91     return ans;
 92 }
 93 inline int Yougth(int u,int v,int kin){
 94     int tp1=top[u],tp2=top[v];
 95     int ans=0;
 96     if(kin==1) ans=-inf;
 97     if(u==v) return queryMAX(1,id[u],id[v]);
 98     while(tp1!=tp2){
 99         if(dep[tp1]<dep[tp2]){//保证dep[tp1]>dep[tp2]  
100             swap(tp1,tp2);
101             swap(u,v);
102         }
103         if(kin==1) ans=max(ans,queryMAX(1,id[tp1],id[u]));
104         else ans+=querySUM(1,id[tp1],id[u]);
105         u=fa[tp1]; tp1=top[u];
106     }
107     // u和 v在同一条重链上 
108     if(dep[u]>dep[v]) swap(u,v);
109     if(kin==1) ans=max(ans,queryMAX(1,id[u],id[v]));
110     else ans+=querySUM(1,id[u],id[v]);
111     return ans;
112 }
113 int main(){
114     scanf("%d",&N);
115     for(int i=1;i<=N-1;i++){
116         int u,v; 
117         scanf("%d%d",&u,&v);
118         to[u].push_back(v); to[v].push_back(u);
119     }
120     dfs1(1,0,1);
121     dfs2(1,1);
122     for(int i=1;i<=N;i++){
123         int w;
124         scanf("%d",&w);
125         val[id[i]]=w;
126     }
127     build(1,1,num);
128     char s[200];
129     scanf("%d",&M);
130     for(int i=1;i<=M;i++){
131         int u,v;
132         scanf("%s%d%d",s,&u,&v);
133         if(s[1]=='M'){
134             printf("%d
",Yougth(u,v,1));
135         }
136         else if(s[1]=='S'){
137             printf("%d
",Yougth(u,v,2));
138         }
139         else if(s[1]=='H'){
140             update(1,id[u],v);
141         }
142     }
143     return 0;
144 }

　　再提供一个本题的造数据程序：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 inline int make_d(){
 4     int k,d;
 5     k=rand()%2;
 6     if(k==0) k=-1;
 7     else k=1;
 8     d=rand()%15000+15000;
 9     return k*d;
10 }
11 int main(){
12     freopen("makedata.out","w",stdout);
13     srand(time(0));
14     int N,M;
15     N=rand()%10+5;
16     cout<<N<<endl;
17     for(int i=2;i<=N;i++){
18         int to=rand()%i;
19         if(to==0) to=1;
20         cout<<i<<" "<<to<<endl;
21     }
22     for(int i=1;i<=N;i++){
23         cout<<make_d()<<" ";
24     }
25     cout<<endl;
26     M=rand()%10+10;
27     cout<<M<<endl;
28     for(int i=1;i<=M;i++){
29         int kin;
30         kin=rand()%3;
31         if(kin==0){
32             cout<<"QMAX"<<" ";
33             int from,to;
34             from=rand()%N+1; to=rand()%N+1;
35             cout<<from<<" "<<to<<endl;
36         }
37         else if(kin==1){
38             cout<<"QSUM"<<" ";
39             int from,to;
40             from=rand()%N+1; to=rand()%N+1;
41             cout<<from<<" "<<to<<endl;
42         }
43         else if(kin==2){
44             cout<<"CHANGE"<<" ";
45             int now;
46             now=rand()%N+1;
47             cout<<now<<" ";
48             cout<<make_d()<<endl;
49         }
50     }
51     return 0;
52 }