[ZJOI2008]树的统计Count

时间限制: 2 s 空间限制: 128000 KB 题目等级 : 大师 Master

题目描述 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 Description

输入文件的第一行为一个整数n，表示节点的个数。

接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。

接下来1行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

输出描述 Output Description

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

样例输入 Sample Input

1 2

2 3

4 1

4 2 1 3

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

数据范围及提示 Data Size & Hint

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

代码实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ls k*2
 4 #define rs k*2+1
 5 using namespace std;
 6 int n,m,l,hs,nl,lfs;
 7 int a,b,ans;
 8 int s[100010],h[100010];
 9 char ch[12];
10 struct node{int k,f,d,sz,ws,p,t;}p[100010];
11 struct nate{int s,n;}e[200020];
12 struct tree{int l,r,s,b;}t[400040];
13 void build(int k,int l,int r){
14     t[k].l=l;t[k].r=r;
15     if(l==r){t[k].s=t[k].b=s[++nl];return;}
16     int mid=(l+r)>>1;
17     build(ls,l,mid);
18     build(rs,mid+1,r);
19     t[k].s=t[ls].s+t[rs].s;
20     t[k].b=max(t[ls].b,t[rs].b);
21 }
22 void change(int k,int l,int r,int v){
23     if(t[k].l==l&&t[k].r==r){t[k].s=t[k].b=v;return;}
24     int mid=(t[k].l+t[k].r)>>1;
25     if(l<=mid) change(ls,l,min(r,mid),v);
26     if(r>mid) change(rs,max(l,mid+1),r,v);
27     t[k].s=t[ls].s+t[rs].s;
28     t[k].b=max(t[ls].b,t[rs].b);
29 }
30 int query1(int k,int l,int r){
31     if(t[k].l==l&&t[k].r==r) return t[k].s;
32     int mid=(t[k].l+t[k].r)>>1,ans=0;
33     if(l<=mid) ans+=query1(ls,l,min(r,mid));
34     if(r>mid) ans+=query1(rs,max(l,mid+1),r);
35     return ans;
36 }
37 int query2(int k,int l,int r){
38     if(t[k].l==l&&t[k].r==r) return t[k].b;
39     int mid=(t[k].l+t[k].r)>>1,ans=-30000;
40     if(l<=mid) ans=max(ans,query2(ls,l,min(r,mid)));
41     if(r>mid) ans=max(ans,query2(rs,max(l,mid+1),r));
42     return ans;
43 }
44 inline void add(int x,int y){e[++hs]=(nate){y,h[x]};h[x]=hs;}
45 void dfs1(int k,int f,int d){
46     p[k].f=f;p[k].d=d;p[k].sz=1;
47     for(int i=h[k];i;i=e[i].n)
48     if(e[i].s!=f){
49         dfs1(e[i].s,k,d+1);
50         p[k].sz+=p[e[i].s].sz;
51         if(p[e[i].s].sz>p[p[k].ws].sz) p[k].ws=e[i].s;
52     }
53 }
54 void dfs2(int k){
55     s[++l]=p[k].k;p[k].p=l;
56     if(p[k].ws){
57         p[p[k].ws].t=p[k].t;
58         dfs2(p[k].ws);
59     }
60     for(int i=h[k];i;i=e[i].n)
61     if(e[i].s!=p[k].ws&&e[i].s!=p[k].f){
62         p[e[i].s].t=e[i].s;
63         dfs2(e[i].s);
64     }
65 }
66 int main(){
67     scanf("%d",&n);
68     for(int i=1;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
69     for(int i=1;i<=n;i++) scanf("%d",&p[i].k);
70     dfs1(1,1,1);
71     dfs2(1);
72     build(1,1,l);
73     scanf("%d",&m);
74     while(m--){
75         scanf("%s%d%d",ch,&a,&b);
76         if(ch[3]=='N') change(1,p[a].p,p[a].p,b);
77         if(ch[3]=='X'){
78             ans=-30000;
79             for(;p[a].t!=p[b].t;a=p[p[a].t].f){
80                 if(p[p[a].t].p<p[p[b].t].p) swap(a,b);
81                 ans=max(ans,query2(1,p[p[a].t].p,p[a].p));
82             }
83             if(p[a].p>p[b].p) swap(a,b);
84             ans=max(ans,query2(1,p[a].p,p[b].p));
85             printf("%d
",ans);
86         }
87         if(ch[3]=='M'){
88             ans=0;
89             for(;p[a].t!=p[b].t;a=p[p[a].t].f){
90                 if(p[p[a].t].p<p[p[b].t].p) swap(a,b);
91                 ans+=query1(1,p[p[a].t].p,p[a].p);
92             }
93             if(p[a].p>p[b].p) swap(a,b);
94             ans+=query1(1,p[a].p,p[b].p);
95             printf("%d
",ans);
96         }
97     }
98     return 0;
99 }

题目来源：CODE[VS]