首页 > 代码库 > BZOJ1036: [ZJOI2008]树的统计Count
BZOJ1036: [ZJOI2008]树的统计Count
1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4980 Solved: 2095
[Submit][Status]
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
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
1
2
2
10
6
5
6
5
16
题解：
原来抄着别人的代码稀里糊涂的过了一遍，什么也没懂。。。
好几次尝试理解树链剖分都失败了。。。
今天又看发现好水，也许是学了splay之后对数据结构又有兴趣了吧。。。
查询的时候借鉴了proverbs的方法，不求LCA，直接往上提，代码量也比较少
http://www.cnblogs.com/proverbs/archive/2013/01/18/2867092.html
代码：
1 {$M 10000000,0,maxlongint} 2 const maxn=30000+100; 3 type node1=record 4 go,next:longint; 5 end; 6 node2=record 7 l,r,mid,mx,sum:longint; 8 end; 9 10 var e:array[0..2*maxn] of node1; 11 t:array[0..4*maxn] of node2; 12 p,a,v,fa,s,head,dep,son,top:array[0..maxn] of longint; 13 i,n,m,x,y,xx,yy,sz,ans,tot:longint; 14 ch:char; 15 procedure swap(var x,y:longint); 16 var t:longint; 17 begin 18 t:=x;x:=y;y:=t; 19 end; 20 procedure insert(x,y:longint); 21 begin 22 inc(tot); 23 e[tot].go:=y;e[tot].next:=head[x];head[x]:=tot; 24 end; 25 function min(x,y:longint):longint; 26 begin 27 if x<y then exit(x) else exit(y); 28 end; 29 function max(x,y:longint):longint; 30 begin 31 if x>y then exit(x) else exit(y); 32 end; 33 34 procedure dfs1(x:longint); 35 var i,j,y:longint; 36 begin 37 j:=0;s[x]:=1; 38 i:=head[x]; 39 while i<>0 do 40 begin 41 y:=e[i].go; 42 if dep[y]=0 then 43 begin 44 dep[y]:=dep[x]+1; 45 fa[y]:=x; 46 dfs1(y); 47 inc(s[x],s[y]); 48 if s[y]>s[j] then j:=y; 49 end; 50 i:=e[i].next; 51 end; 52 son[x]:=j; 53 end; 54 procedure dfs2(x,chain:longint); 55 var i,y:longint; 56 begin 57 inc(sz);p[x]:=sz;top[x]:=chain; 58 if son[x]<>0 then dfs2(son[x],chain); 59 i:=head[x]; 60 while i<>0 do 61 begin 62 y:=e[i].go; 63 if (p[y]=0) and (y<>son[x]) then dfs2(y,y); 64 i:=e[i].next; 65 end; 66 end; 67 procedure pushup(k:longint); 68 begin 69 t[k].mx:=max(t[k<<1].mx,t[k<<1+1].mx); 70 t[k].sum:=t[k<<1].sum+t[k<<1+1].sum; 71 end; 72 73 procedure build(k,x,y:longint); 74 begin 75 with t[k] do 76 begin 77 l:=x;r:=y;mid:=(l+r)>>1; 78 if l=r then begin mx:=a[l];sum:=a[l];exit;end; 79 build(k<<1,l,mid);build(k<<1+1,mid+1,r); 80 pushup(k); 81 end; 82 end; 83 procedure change(k,x,y:longint); 84 begin 85 with t[k] do 86 begin 87 if l=r then begin mx:=y;sum:=y;exit;end; 88 if x<=mid then change(k<<1,x,y) 89 else change(k<<1+1,x,y); 90 pushup(k); 91 end; 92 end; 93 94 function getmx(k,x,y:longint):longint; 95 begin 96 with t[k] do 97 begin 98 if (l=x) and (r=y) then exit(mx); 99 if y<=mid then exit(getmx(k<<1,x,y))100 else if x>mid then exit(getmx(k<<1+1,x,y))101 else exit(max(getmx(k<<1,x,mid),getmx(k<<1+1,mid+1,y)));102 end;103 end;104 function getsum(k,x,y:longint):longint;105 begin106 with t[k] do107 begin108 if (l=x) and (r=y) then exit(sum);109 if y<=mid then exit(getsum(k<<1,x,y))110 else if x>mid then exit(getsum(k<<1+1,x,y))111 else exit(getsum(k<<1,x,mid)+getsum(k<<1+1,mid+1,y));112 end;113 end;114 115 procedure init;116 begin117 readln(n);118 for i:=1 to n-1 do begin readln(x,y);insert(x,y);insert(y,x);end;119 dep[1]:=1;120 dfs1(1);121 dfs2(1,1);122 for i:=1 to n do read(v[i]);123 for i:=1 to n do a[p[i]]:=v[i];124 build(1,1,n);125 end;126 procedure solvemx;127 begin128 ans:=-maxlongint;129 while ch<>‘ ‘ do read(ch);130 readln(x,y);131 while top[x]<>top[y] do132 begin133 if dep[top[x]]<dep[top[y]] then swap(x,y);134 ans:=max(ans,getmx(1,p[top[x]],p[x]));135 x:=fa[top[x]];136 end;137 if dep[x]>dep[y] then swap(x,y);138 ans:=max(ans,getmx(1,p[x],p[y]));139 writeln(ans);140 end;141 procedure solvesum;142 begin143 ans:=0;144 while ch<>‘ ‘ do read(ch);145 readln(x,y);146 while top[x]<>top[y] do147 begin148 if dep[top[x]]<dep[top[y]] then swap(x,y);149 inc(ans,getsum(1,p[top[x]],p[x]));150 x:=fa[top[x]];151 end;152 if dep[x]>dep[y] then swap(x,y);153 inc(ans,getsum(1,p[x],p[y]));154 writeln(ans);155 end;156 157 procedure main;158 begin159 readln(m);160 for i:=1 to m do161 begin162 read(ch);163 if ch=‘C‘ then164 begin165 while ch<>‘ ‘ do read(ch);readln(x,y);166 change(1,p[x],y);167 end168 else169 begin170 read(ch);171 if ch=‘M‘ then solvemx else solvesum;172 end;173 end;174 end;175 176 begin177 assign(input,‘input.txt‘);assign(output,‘output.txt‘);178 reset(input);rewrite(output);179 init;180 main;181 close(input);close(output);182 end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。