# 1036: [ZJOI2008]树的统计Count

## 1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 7496  Solved: 3078

[Submit][Status][Discuss]

## 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

## Source

```  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;
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
168      for i:=1 to n do a[i]:=nil;
169      for i:=1 to n-1 do
170          begin
173          end;
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);
181      for i:=1 to m do
182          begin
184               case upcase(ch) of
185                    'M':begin
187                             writeln(treemax(j,k));
188                    end;
189                    'S':begin
191                             writeln(treesum(j,k));
192                    end;
193                    'H':begin
195                             treechange(j,a1);
196                    end;
197               end;
198          end;
200 end.```

0 条评论

• ### 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者 Time Limit: 3 Sec  Memory Limit: 128...

• ### 2929: [Poi1999]洞穴攀行

2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

• ### 算法模板——线段树3（区间覆盖值+区间求和）

实现功能——1：区间覆盖值；2：区间求和 相比直接的区间加，这个要注重顺序，因为操作有顺序之分。所以这里面的tag应该有个pushup操作（本程序中的ext） ...

• ### 1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

• ### 2929: [Poi1999]洞穴攀行

2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

• ### 3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

3390: [Usaco2004 Dec]Bad Cowtractors牛的报复 Time Limit: 1 Sec  Memory Limit: 128 MB...

• ### 1339 / 1163: [Baltic2008]Mafia

1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

• ### 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者 Time Limit: 3 Sec  Memory Limit: 128...

• ### 3038: 上帝造题的七分钟2

3038: 上帝造题的七分钟2 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 662  Solved: 302...

• ### 1622: [Usaco2008 Open]Word Power 名字的能量

1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...