bzoj1036[ZJOI2008]树的统计Count【树链剖分】
第一道树链剖分题~
就是树链剖分的裸题啦~直接套模板就行,关于树链剖分的讲解点这里。
代码:
type node=record l,r,max,sum:longint; end; var t:array[1..65536]of node; v,next:array[1..60000]of longint; a,d,num,dep,top,f,son,tree,pre:array[1..30000]of longint; n,m,i,j,k,p,q,tot:longint; c:char; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure adde(uu,vv:longint); begin inc(k); v[k]:=vv; next[k]:=a[uu]; a[uu]:=k; inc(k); v[k]:=uu; next[k]:=a[vv]; a[vv]:=k; end; procedure dfs1(k,fa,d:longint); var i:longint; begin dep[k]:=d; f[k]:=fa; num[k]:=1; i:=a[k]; while i<>0 do begin if v[i]<>fa then begin dfs1(v[i],k,d+1); num[k]:=num[k]+num[v[i]]; if (son[k]=0) or (num[v[i]]>num[son[k]]) then son[k]:=v[i]; end; i:=next[i]; end; end; procedure dfs2(k,n:longint); var i:longint; begin top[k]:=n; inc(tot); tree[k]:=tot; pre[tree[k]]:=k; if son[k]=0 then exit; dfs2(son[k],n); i:=a[k]; while i<>0 do begin if (v[i]<>son[k]) and (v[i]<>f[k]) then dfs2(v[i],v[i]); i:=next[i]; end; end; procedure build(k,l,r:longint); var mid:longint; begin t[k].l:=l; t[k].r:=r; if l=r then begin t[k].sum:=d[pre[l]]; t[k].max:=d[pre[r]]; exit; end; mid:=(l+r) shr 1; build(k shl 1,l,mid); build(k shl 1 or 1,mid+1,r); t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum; t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max); end; function qqmax(k,l,r:longint):longint; var mid,ans:longint; begin if (t[k].l>=l) and (t[k].r<=r) then exit(t[k].max); mid:=(t[k].l+t[k].r) shr 1; ans:=-2147483647; if l<=mid then ans:=max(ans,qqmax(k shl 1,l,r)); if r>mid then ans:=max(ans,qqmax(k shl 1 or 1,l,r)); t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum; t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max); exit(ans); end; function qmax(var p,q:longint):longint; var x,y,ans,t:longint; begin x:=top[p]; y:=top[q]; ans:=-2147483647; while x<>y do begin if dep[x]<dep[y] then begin t:=x; x:=y; y:=t; t:=p; p:=q; q:=t; end; ans:=max(ans,qqmax(1,tree[x],tree[p])); p:=f[x]; x:=top[p]; end; if dep[p]>dep[q] then ans:=max(ans,qqmax(1,tree[q],tree[p])) else ans:=max(ans,qqmax(1,tree[p],tree[q])); exit(ans); end; function qqsum(k,l,r:longint):longint; var mid,ans:longint; begin if (t[k].l>=l) and (t[k].r<=r) then exit(t[k].sum); mid:=(t[k].l+t[k].r) shr 1; ans:=0; if l<=mid then ans:=ans+qqsum(k shl 1,l,r); if r>mid then ans:=ans+qqsum(k shl 1 or 1,l,r); t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum; t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max); exit(ans); end; function qsum(var p,q:longint):longint; var x,y,ans,t:longint; begin x:=top[p]; y:=top[q]; ans:=0; while x<>y do begin if dep[x]<dep[y] then begin t:=x; x:=y; y:=t; t:=p; p:=q; q:=t; end; ans:=ans+qqsum(1,tree[x],tree[p]); p:=f[x]; x:=top[p]; end; if dep[p]>dep[q] then ans:=ans+qqsum(1,tree[q],tree[p]) else ans:=ans+qqsum(1,tree[p],tree[q]); exit(ans); end; procedure update(k,x,o:longint); var mid:longint; begin if t[k].l=t[k].r then begin t[k].sum:=t[k].sum+o; t[k].max:=t[k].max+o; exit; end; mid:=(t[k].l+t[k].r) shr 1; if x<=mid then update(k shl 1,x,o) else update(k shl 1 or 1,x,o); t[k].sum:=t[k shl 1].sum+t[k shl 1 or 1].sum; t[k].max:=max(t[k shl 1].max,t[k shl 1 or 1].max); end; begin readln(n); for i:=1 to n-1 do begin readln(p,q); adde(p,q); end; for i:=1 to n do read(d[i]); dfs1(1,0,1); dfs2(1,1); build(1,1,n); readln(m); repeat dec(m); read(c); read(c); if c='M' then begin for i:=1 to 3 do read(c); readln(p,q); writeln(qmax(p,q)); end; if c='S' then begin for i:=1 to 3 do read(c); readln(p,q); writeln(qsum(p,q)); end; if c='H' then begin for i:=1 to 5 do read(c); readln(p,q); update(1,tree[p],q-d[p]); d[p]:=q; end; until m=0; end.
之前有几个小地方有点问题调试了一会。。。
发表回复