1984: 月下“毛景树”

1984: 月下“毛景树”

Time Limit: 20 Sec  Memory Limit: 64 MB

Submit: 1003  Solved: 324

[Submit][Status][Discuss]

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏pangguoming

JDBC上关于数据库中多表操作一对多关系和多对多关系的实现方法

我们知道,在设计一个Java bean的时候,要把这些BEAN 的数据存放在数据库中的表结构,然而这些数据库中的表直接又有些特殊的关系,例如员工与部门直接有一对...

8697
来自专栏更流畅、简洁的软件开发方式

我的数据访问函数库的源代码(三)——返回结构数组

/* 2008 4 25 更新 */ 我的数据访问函数库的源码。整个类有1400行,原先就是分开来写的,现在更新后还是分开来发一下吧。 第三部分:返回结构 ...

2076
来自专栏数据结构与算法

BZOJ2438: [中山市选2011]杀人游戏(tarjan)

当然有一种例外情况是\(1 -> 3, 2 -> 3\),也就是存在一个孤立点,判掉即可

1112
来自专栏数据结构与算法

Day5上午解题报告

预计分数:100+40+30=170 实际假分数:0+0+0=0 CE*3 实际真分数:60+50+0=110 老师没把我的程序放的文件夹里面,于是。。。。。 ...

3506
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第六章 Kotlin函数式编程(FP)函数指针复合函数

看了下面的复合函数的例子,你会发现Kotlin的FP的实现相当简洁。(跟纯数学的表达式,相当接近了)

731
来自专栏Golang语言社区

Golang中time包用法--转

time包中包括两类时间:时间点(某一时刻)和时常(某一段时间) 1时间常量(时间格式化) const ( ANSIC = "Mon Jan...

1.5K8
来自专栏Ldpe2G的个人博客

Graphviz4S ---- 在Scala中使用DOT语言绘图的开源工具

之前需要在Scala中用到类似python的graphviz库的功能,用来在Mxnet中可视化网络结构,

1714
来自专栏算法修养

PAT 甲级 1021 Deepest Root (并查集,树的遍历)

1021. Deepest Root (25) 时间限制 1500 ms 内存限制 65536 kB 代码长度限制 16000 B ...

3587
来自专栏小樱的经验随笔

Codeforces 839D Winter is here【数学:容斥原理】

D. Winter is here time limit per test:3 seconds memory limit per test:256 megaby...

2826
来自专栏Ldpe2G的个人博客

Graphviz4S ---- 在Scala中使用DOT语言绘图的开源工具

2106

扫码关注云+社区

领取腾讯云代金券