1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 17908 Solved: 7296
[Submit][Status][Discuss]
Description
一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. 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
1 #include "bits/stdc++.h"
2 #define mem(a,b) memset(a,b,sizeof(a))
3 using namespace std;
4 typedef long long LL;
5 const int MAX=30005;
6 int n,m;
7 int a[MAX],tot,ttt;
8 int head[MAX],adj[MAX<<1],next[MAX<<1];
9 int top[MAX],size[MAX],fa[MAX],son[MAX],rank[MAX],id[MAX],deep[MAX];
10 inline int read(){
11 int an=0,x=1;char c=getchar();
12 while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
13 while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}
14 return x*an;
15 }
16 void addedge(int u,int v){
17 tot++;
18 adj[tot]=v;
19 next[tot]=head[u];
20 head[u]=tot;
21 }
22 void init(){
23 int i,j;
24 int u,v;
25 n=read();
26 mem(head,0),mem(son,0);
27 tot=ttt=0;
28 for (i=1;i<n;i++){
29 u=read();v=read();
30 addedge(u,v);
31 addedge(v,u);
32 }
33 for (i=1;i<=n;i++)
34 a[i]=read();
35 m=read();
36 deep[0]=0;
37 }
38 void dfs1(int x,int ff){
39 int i,j;
40 fa[x]=ff;
41 size[x]=1;deep[x]=deep[ff]+1;
42 for (i=head[x];i;i=next[i]){
43 if (adj[i]==ff) continue;
44 dfs1(adj[i],x);
45 if (!son[x] || size[adj[i]]>size[son[x]]){
46 son[x]=adj[i];
47 }
48 size[x]+=size[adj[i]];
49 }
50 }
51 void dfs2(int x,int tp){
52 int i,j;
53 top[x]=tp;
54 id[x]=++ttt;rank[ttt]=x;
55 if (son[x]) dfs2(son[x],tp);
56 for (i=head[x];i;i=next[i]){
57 if (adj[i]==son[x] || adj[i]==fa[x]) continue;
58 dfs2(adj[i],adj[i]);
59 }
60 }
61 #define lson rt<<1,l,m
62 #define rson rt<<1|1,m+1,r
63 int sum[MAX<<2],mx[MAX<<2];
64 void PushUp(int rt){
65 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
66 mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
67 }
68 void build(int rt,int l,int r){
69 if (l==r){
70 sum[rt]=a[rank[l]];
71 mx[rt]=sum[rt];
72 return;
73 }
74 int m=(l+r)>>1;
75 build(lson);
76 build(rson);
77 PushUp(rt);
78 }
79 void update(int rt,int l,int r,int x,int z){
80 if (l==r){
81 sum[rt]=z;
82 mx[rt]=z;
83 return;
84 }
85 int m=(l+r)>>1;
86 if (x<=m) update(lson,x,z);
87 if (x>m) update(rson,x,z);
88 PushUp(rt);
89 }
90 int search1(int rt,int l,int r,int x,int y){
91 if (x<=l && r<=y)
92 return sum[rt];
93 int res=0;
94 int m=(l+r)>>1;
95 if (x<=m) res+=search1(lson,x,y);
96 if (y>m) res+=search1(rson,x,y);
97 PushUp(rt);
98 return res;
99 }
100 int search2(int rt,int l,int r,int x,int y){
101 if (x<=l && r<=y)
102 return mx[rt];
103 int res=-2147483647;
104 int m=(l+r)>>1;
105 if (x<=m) res=max(res,search2(lson,x,y));
106 if (y>m) res=max(res,search2(rson,x,y));
107 PushUp(rt);
108 return res;
109 }
110 int calc1(int x,int y){
111 int an=0;
112 while (top[x]!=top[y]){
113 if (deep[top[x]]<deep[top[y]]) swap(x,y);
114 an+=search1(1,1,n,id[top[x]],id[x]);
115 x=fa[top[x]];
116 }
117 if (deep[x]>deep[y]) swap(x,y);
118 an+=search1(1,1,n,id[x],id[y]);
119 return an;
120 }
121 int calc2(int x,int y){
122 int an=-2147483647;
123 while (top[x]!=top[y]){
124 if (deep[top[x]]<deep[top[y]]) swap(x,y);//注意:是比较他们的top的深度!!
125 an=max(an,search2(1,1,n,id[top[x]],id[x]));
126 x=fa[top[x]];
127 }
128 if (deep[x]>deep[y]) swap(x,y);
129 an=max(an,search2(1,1,n,id[x],id[y]));
130 return an;
131 }
132 int main(){
133 freopen ("count.in","r",stdin);
134 freopen ("count.out","w",stdout);
135 int i,j,x,y;char s[10];
136 init();
137 dfs1(1,0),dfs2(1,1);
138 build(1,1,n);
139 for (i=1;i<=m;i++){
140 scanf("%s",s);
141 x=read();y=read();
142 if (s[1]=='H'){
143 update(1,1,n,id[x],y);
144 }
145 if (s[1]=='S'){
146 printf("%d\n",calc1(x,y));
147 }
148 if (s[1]=='M'){
149 printf("%d\n",calc2(x,y));
150 }
151 }
152 return 0;
153