1036: [ZJOI2008]树的统计Count
1036: [ZJOI2008]树的统计Count
HansBug
发布于 2018-04-11 11:05:47
发布于 2018-04-11 11:05:47
1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 7496 Solved: 3078
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
题解：phile神犇推荐的链剖模板题，一直不知道为啥挂掉，急死掉= =，最后发现居然把inline去掉就A了QAQ，逗我= =
事实证明——（引用phile神犇的原话）黑科技不可滥用TT
1 type
2 point=^node;
3 node=record
4 g:longint;
5 next:point;
6 end;
7 var
8 i,j,k,l,m,n,tot,root:longint;a1:int64;
9 a:array[0..100000] of point;ch:char;
10 d,e:array[0..500000] of int64;
11 len,son,siz,top,list,f,num,anum:array[0..100000] of longint;
12 c:array[0..20,0..100000] of longint;
13 function min(x,y:longint):longint;
14 begin
15 if x<y then min:=x else min:=y;
16 end;
17 function max(x,y:longint):longint;
18 begin
19 if x>y then max:=x else max:=y;
20 end;
21 procedure swap(var x,y:longint);
22 var z:longint;
23 begin
24 z:=x;x:=y;y:=z;
25 end;
26 procedure add(x,y:longint);
27 var p:point;
28 begin
29 new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
30 end;
31 procedure dfs(y,x:longint);
32 var p:point;
33 begin
34 c[0,x]:=y;siz[x]:=1;len[x]:=len[y]+1;son[x]:=0;
35 p:=a[x];
36 while p<>nil do
37 begin
38 if p^.g<>y then
39 begin
40 dfs(x,p^.g);
41 inc(siz[x],siz[p^.g]);
42 if (son[x]=0) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
43 end;
44 p:=p^.next;
45 end;
46 end;
47 procedure dfs2(y,x,z:longint);
48 var p:point;
49 begin
50 top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
51 if son[x]<>0 then dfs2(x,son[x],z);p:=a[x];
52 while p<>nil do
53 begin
54 if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
55 p:=p^.next;
56 end;
57 end;
58 procedure built(z,x,y:longint);
59 begin
60 if x=y then
61 begin
62 list[x]:=z;
63 d[z]:=f[anum[x]];
64 e[z]:=d[z];
65 end
66 else
67 begin
68 built(z*2,x ,(x+y) div 2);
69 built(z*2+1,(x+y) div 2+1,y);
70 d[z]:=d[z*2]+d[z*2+1];
71 if e[z*2+1]>e[z*2] then e[z]:=e[z*2+1] else e[z]:=e[z*2];
72 end;
73 end;
74 procedure change(x:longint;y:int64);
75 begin
76 x:=list[x];d[x]:=y;e[x]:=y;x:=x div 2;
77 while x>0 do
78 begin
79 d[x]:=d[x*2]+d[x*2+1];
80 if e[x*2+1]>e[x*2] then e[x]:=e[x*2+1] else e[x]:=e[x*2];
81 x:=x div 2;
82 end;
83 end;
84 function sum(z,x,y,l,r:longint):int64;
85 begin
86 if l>r then exit(0);
87 if (x=l) and (y=r) then exit(d[z]);
88 exit(sum(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2))+sum(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r));
89 end;
90 function getmax(z,x,y,l,r:longint):int64;
91 var a1,a2:int64;
92 begin
93 if l>r then exit(-maxlongint*maxlongint);
94 if (x=l) and (y=r) then exit(e[z]);
95 a1:=getmax(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2));
96 a2:=getmax(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r);
97 if a1>a2 then exit(a1) else exit(a2);
98 end;
99 function getup(x,y:longint):longint;
100 var i:longint;
101 begin
102 i:=0;
103 while y>0 do
104 begin
105 if odd(y) then x:=c[i,x];
106 inc(i);y:=y div 2;
107 end;
108 exit(x);
109 end;
110 function getcom(x,y:longint):longint;
111 var i:longint;
112 begin
113 if len[x]<len[y] then swap(x,y);
114 x:=getup(x,len[x]-len[y]);
115 if x=y then exit(x);
116 for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
117 if c[i,x]<>c[i,y] then
118 begin
119 x:=c[i,x];
120 y:=c[i,y];
121 end;
122 exit(c[0,x]);
123 end;
124 procedure treechange(x:longint;y:int64);
125 begin
126 change(num[x],y);
127 end;
128 function treesum(x,y:longint):int64;
129 var i,z:longint;
130 begin
131 z:=getcom(x,y);treesum:=0;
132 repeat
133 if len[top[x]]<len[z] then i:=z else i:=top[x];
134 inc(treesum,sum(1,1,n,num[i],num[x]));
135 if i=z then break;
136 x:=c[0,i];
137 until false;
138 repeat
139 if len[top[y]]<len[z] then i:=z else i:=top[y];
140 inc(treesum,sum(1,1,n,num[i],num[y]));
141 if i=z then break;
142 y:=c[0,i];
143 until false;
144 dec(treesum,sum(1,1,n,num[z],num[z]));
145 end;
146 function treemax(x,y:longint):int64;
147 var i,z:longint;a1:int64;
148 begin
149 treemax:=-maxlongint*maxlongint;
150 z:=getcom(x,y);
151 repeat
152 if len[top[x]]<len[z] then i:=z else i:=top[x];
153 a1:=getmax(1,1,n,num[i],num[x]);
154 if a1>treemax then treemax:=a1;
155 if i=z then break;
156 x:=c[0,i];
157 until false;
158 repeat
159 if len[top[y]]<len[z] then i:=z else i:=top[y];
160 a1:=getmax(1,1,n,num[i],num[y]);
161 if a1>treemax then treemax:=a1;
162 if i=z then break;
163 y:=c[0,i];
164 until false;
165 end;
166 begin
167 readln(n);
168 for i:=1 to n do a[i]:=nil;
169 for i:=1 to n-1 do
170 begin
171 readln(j,k);
172 add(j,k);add(k,j);
173 end;
174 for i:=1 to n do read(f[i]);readln;
175 root:=random(n)+1;dfs(0,root);dfs2(0,root,root);
176 for i:=1 to trunc(round(ln(n)/ln(2)))+1 do
177 for j:=1 to n do
178 c[i,j]:=c[i-1,c[i-1,j]];
179 built(1,1,n);
180 readln(m);
181 for i:=1 to m do
182 begin
183 read(ch,ch);
184 case upcase(ch) of
185 'M':begin
186 readln(ch,ch,j,k);
187 writeln(treemax(j,k));
188 end;
189 'S':begin
190 readln(ch,ch,j,k);
191 writeln(treesum(j,k));
192 end;
193 'H':begin
194 readln(ch,ch,ch,ch,j,a1);
195 treechange(j,a1);
196 end;
197 end;
198 end;
199 readln;
200 end.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录