1036: [ZJOI2008]树的统计Count

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 7496  Solved: 3078

[Submit][Status][Discuss]

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.

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 84 Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the...

1819
来自专栏Java3y

Map集合、散列表、红黑树介绍

1883
来自专栏人工智能LeadAI

机器学习实战 | 第三章:集成学习

集成学习肯定是在实战中最不可或缺的思想了.毕竟都想把错误率低一点,再低一点,再低一点.看看kaggle大量的集成学习就知道这节肯定绕不过去了. 在这里,仅仅说...

2945
来自专栏前端儿

重建二叉树

题目很简单,给你一棵二叉树的后序和中序序列,求出它的前序序列(So easy!)。

2321
来自专栏向治洪

高级聚类

FuzzyKmeans 在对数据进行聚类时,最常用的方法应该是kmeans,但是kmean只能保证每一条待聚类的数据划分到一个类别,针对一条数据可以被划分到多个...

2068
来自专栏ml

HDUOJ----旋转的二进制

旋转的二进制 Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java...

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

BZOJ1857: [Scoi2010]传送带(三分套三分)

1020
来自专栏逍遥剑客的游戏开发

D3D深度测试和Alpha混合

2675
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

2333
来自专栏nnngu

数据结构09 哈夫曼树

这一篇要总结的是树中的哈夫曼树(Huffman Tree),我想从以下几点对其进行总结: 1、什么是哈夫曼树 2、如何构建哈夫曼树 3、哈夫曼编码 4、代码实现...

3107

扫码关注云+社区

领取腾讯云代金券