1984: 月下“毛景树”
1984: 月下“毛景树”
HansBug
发布于 2018-04-11 11:04:59
发布于 2018-04-11 11:04:59
1984: 月下“毛景树”
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 1003 Solved: 324
Description
毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数： Change k w：将第k条树枝上毛毛果的个数改变为w个。 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问： Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。
Input
第一行一个正整数N。 接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。
Output
对于毛毛虫的每个询问操作，输出一个答案。
Sample Input
4 1 2 8 1 3 7 3 4 9 Max 2 4 Cover 2 4 5 Add 1 4 10 Change 1 16 Max 2 4 Stop
Sample Output
9 16 【Data Range】 1<=N<=100,000，操作+询问数目不超过100,000。 保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。
HINT
Source
题解：不用多说，又是一个树链剖分。。。只不过这里面要维护的是树上各个边的权值，不再是点的权值了，于是本蒟蒻由于懒得想边维护怎么搞所以直接想了个神(dou)奇(bi)办法将边维护转化为了点维护问题——
对于一个边而言，显然连接着两个点，然后当我们建立完有根树之后，每个边则会对应着唯一的一个下方的节点（而且显然除了根节点之外每个点都刚刚好对应一条边），然后边的维护就成功转化为了点的维护问题了，唯一的不同在于当你每次进行树上操作的时候记得一定要排除两个点LCA位置的那个点（HansBug：因为那个点对应着该条链之外的一条边，而别的点对应的则均为该链上的^_^）
然后接下来就是漫漫的Debug之路了，然后弄来弄去发现还是爆栈了TT，其实只要一个编译开关就可以啦，详见程序第一行
1 /**************************************************************
2 Problem: 1984
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:13800 ms
7 Memory:58596 kb
8 ****************************************************************/
9
10 {$M 6552000,0,655360000}
11 type
12 point=^node;
13 node=record
14 g,f:longint;
15 next:point;w:int64;
16 end;
17 var
18 i,j,k,l,m,n,tot,root:longint;ch:char;
19 a:array[0..100005] of point;
20 e:array[0..1000005,0..3] of int64;
21 c:array[0..20,0..100005] of longint;
22 d:array[0..1000005] of int64;
23 f:array[0..100005] of int64;
24 top,tip,len,siz,son,g,num,anum:array[0..100005] of longint;
25 procedure swap(var x,y:longint);
26 var z:longint;
27 begin
28 z:=x;x:=y;y:=z;
29 end;
30 function max(x,y:longint):longint;
31 begin
32 if x>y then max:=x else max:=y;
33 end;
34 function min(x,y:longint):longint;
35 begin
36 if x<y then min:=x else min:=y;
37 end;
38 procedure add(x,y,z,t:longint);
39 var p:point;
40 begin
41 new(p);p^.g:=y;p^.w:=z;p^.f:=t;
42 p^.next:=a[x];a[x]:=p;
43 end;
44 procedure dfs(y,x:longint);
45 var p:point;
46 begin
47 len[x]:=len[y]+1;
48 c[0,x]:=y;siz[x]:=1;
49 son[x]:=0;p:=a[x];
50 while p<>nil do
51 begin
52 if p^.g<>y then
53 begin
54 dfs(x,p^.g);tip[p^.w]:=p^.g;f[p^.g]:=p^.f;
55 if (son[x]=0) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
56 inc(siz[x],siz[p^.g]);
57 end;
58 p:=p^.next;
59 end;
60 end;
61 procedure dfs2(y,x,z:longint);
62 var p:point;
63 begin
64 top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
65 if son[x]<>0 then dfs2(x,son[x],z);p:=a[x];
66 while p<>nil do
67 begin
68 if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
69 p:=p^.next;
70 end;
71 end;
72 procedure ext(z,x,y:longint);
73 begin
74 if e[z,1]<>0 then
75 begin
76 d[z]:=e[z,2];
77 if x<>y then
78 begin
79 e[z*2,1]:=1;e[z*2,2]:=e[z,2];
80 e[z*2+1,1]:=1;e[z*2+1,2]:=e[z,2];
81 end;
82 e[z,2]:=0;e[z,1]:=0;e[z,3]:=0;
83 end
84 else if e[z,3]<>0 then
85 begin
86 inc(d[z],e[z,3]);
87 if x<>y then
88 begin
89 if e[z*2,1]<>0 then ext(z*2,x,(x+y) div 2);
90 if e[z*2+1,1]<>0 then ext(z*2+1,(x+y) div 2+1,y);
91 inc(e[z*2,3],e[z,3]);
92 inc(e[z*2+1,3],e[z,3]);
93 end;
94 e[z,3]:=0;e[z,2]:=0;e[z,1]:=0;
95 end;
96 end;
97 procedure built(z,x,y:longint);
98 begin
99 if x=y then
100 d[z]:=f[anum[x]]
101 else
102 begin
103 built(z*2,x,(x+y) div 2);
104 built(z*2+1,(x+y) div 2+1,y);
105 if d[z*2]>d[z*2+1] then d[z]:=d[z*2] else d[z]:=d[z*2+1];
106 end;
107 e[z,1]:=0;e[z,2]:=0;e[z,3]:=0;
108 end;
109 function addd(z,x,y,l,r:longint;t:int64):int64;
110 var a1,a2:int64;
111 begin
112 if l>r then
113 begin
114 ext(z,x,y);
115 exit(d[z]);
116 end;
117 ext(z,x,y);if (x=l) and (y=r) then
118 begin
119 inc(e[z,3],t);
120 exit(d[z]+e[z,3]);
121 end;
122 a1:=addd(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
123 a2:=addd(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
124 if a1>a2 then d[z]:=a1 else d[z]:=a2;
125 exit(d[z]);
126 end;
127 function cover(z,x,y,l,r:longint;t:int64):int64;
128 var a1,a2:int64;
129 begin
130
131 if l>r then
132 begin
133 ext(z,x,y);
134 exit(d[z]);
135 end;
136 if (x=l) and (y=r) then
137 begin
138 e[z,1]:=1;
139 e[z,2]:=t;
140 exit(t);
141 end;
142 ext(z,x,y);
143 a1:=cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
144 a2:=cover(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
145 if a1>a2 then d[z]:=a1 else d[z]:=a2;
146 exit(d[z]);
147 end;
148 function getmax(z,x,y,l,r:longint):int64;
149 begin
150 if l>r then exit(-maxlongint);
151 if e[z,1]<>0 then exit(e[z,2]);
152 ext(z,x,y);
153 if (x=l) and (y=r) then exit(d[z]);
154 exit(max(getmax(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2)),getmax(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)));
155 end;
156 function getup(x,y:longint):longint;
157 var i:longint;
158 begin
159 i:=0;
160 while y<>0 do
161 begin
162 if odd(y) then x:=c[i,x];
163 inc(i);y:=y div 2;
164 end;
165 exit(x);
166 end;
167 function getcom(x,y:longint):longint;
168 var i:longint;
169 begin
170 if len[x]<len[y] then swap(x,y);
171 x:=getup(x,len[x]-len[y]);
172 if x=y then exit(x);
173 for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
174 if c[i,x]<>c[i,y] then
175 begin
176 x:=c[i,x];
177 y:=c[i,y];
178 end;
179 exit(c[0,x]);
180 end;
181 procedure treechange(x,y:longint;t:int64);
182 var i,z,z1:longint;
183 begin
184 z:=getcom(x,y);
185 if x<>z then
186 begin
187 z1:=getup(x,len[x]-len[z]-1);
188 repeat
189 if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
190 cover(1,1,n,num[i],num[x],t);
191 if i=z1 then break;
192 x:=c[0,i];
193 until false;
194 end;
195 if y<>z then
196 begin
197 z1:=getup(y,len[y]-len[z]-1);
198 repeat
199 if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
200 cover(1,1,n,num[i],num[y],t);
201 if i=z1 then break;
202 y:=c[0,i];
203 until false;
204 end;
205 end;
206 procedure treeadd(x,y:longint;t:int64);
207 var z,i,z1:longint;
208 begin
209 z:=getcom(x,y);
210 if x<>z then
211 begin
212 z1:=getup(x,len[x]-len[z]-1);
213 repeat
214 if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
215 addd(1,1,n,num[i],num[x],t);
216 if i=z1 then break;
217 x:=c[0,i];
218 until false;
219 end;
220 if y<>z then
221 begin
222 z1:=getup(y,len[y]-len[z]-1);
223 repeat
224 if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
225 addd(1,1,n,num[i],num[y],t);
226 if i=z1 then break;
227 y:=c[0,i];
228 until false;
229 end;
230 end;
231 function treemax(x,y:longint):int64;
232 var i,z,z1:longint;a1:int64;
233 begin
234 z:=getcom(x,y);treemax:=0;
235 if x<>z then
236 begin
237 z1:=getup(x,len[x]-len[z]-1);
238 repeat
239 if len[top[x]]<len[z1] then i:=z1 else i:=top[x];
240 a1:=getmax(1,1,n,num[i],num[x]);
241 if a1>treemax then treemax:=a1;
242 if i=z1 then break;
243 x:=c[0,i];
244 until false;
245 end;
246 if y<>z then
247 begin
248 z1:=getup(y,len[y]-len[z]-1);
249 repeat
250 if len[top[y]]<len[z1] then i:=z1 else i:=top[y];
251 a1:=getmax(1,1,n,num[i],num[y]);
252 if a1>treemax then treemax:=a1;
253 if i=z1 then break;
254 y:=c[0,i];
255 until false;
256 end;
257 end;
258 begin
259 readln(n);
260 for i:=1 to n do a[i]:=nil;
261 for i:=1 to n-1 do
262 begin
263 readln(j,k,l);
264 add(j,k,i,l);add(k,j,i,l);
265 end;
266 root:=random(n)+1;dfs(0,root);dfs2(0,root,root);
267 for i:=1 to trunc(round(ln(n)/ln(2))) do
268 for j:=1 to n do
269 c[i,j]:=c[i-1,c[i-1,j]];
270 built(1,1,n);
271 while not(eof) do
272 begin
273 read(ch,ch);
274 case upcase(ch) of
275 'A':begin
276 readln(ch,i,j);
277 writeln(treemax(i,j));
278 end;
279 'O':begin
280 readln(ch,ch,ch,i,j,k);
281 treechange(i,j,k);
282 end;
283 'D':begin
284 readln(ch,i,j,k);
285 treeadd(i,j,k);
286 end;
287 'H':begin
288 readln(ch,ch,ch,ch,i,j);
289 treechange(c[0,tip[i]],tip[i],j);
290 end;
291 'T':halt;
292 end;
293 end;
294 end.本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录