首页 > 代码库 > bzoj4390: [Usaco2015 dec]Max Flow(LCA+树上差分)
bzoj4390: [Usaco2015 dec]Max Flow(LCA+树上差分)
题目大意:给出一棵树,n(n<=5w)个节点,k(k<=10w)次修改,每次给定s和t,把s到t的路径上的点权+1,问k次操作后最大点权。
对于每次修改,给s和t的点权+1,给lca(s,t)和lca(s,t)的父亲的点权-1,每一个点的权就是它与它的子树权和,实际上就是树上的差分,又涨姿势了。。。
代码如下:
uses math;type point=^rec; rec=record data:longint; next:point; end;var n,m,x,y,i,ans,fa,kk:longint; k:point; d,siz,sum:array[0..100000]of longint; a:array[0..100000]of point; p:array[0..100000,0..20]of longint;procedure dfs(x,fa:longint);var k:point; l:longint;begin d[x]:=d[fa]+1; l:=trunc(ln(n)/ln(2)); p[x,0]:=fa; for i:=1 to l do p[x,i]:=p[p[x,i-1],i-1]; k:=a[x]; while k<>nil do begin if k^.data<>fa then dfs(k^.data,x); k:=k^.next; end;end;function lca(x,y:longint):longint;var t,l,i:longint;begin if d[x]>d[y] then begin t:=x;x:=y;y:=t; end; if d[x]<d[y] then begin l:=trunc(ln(d[y]-d[x])/ln(2))+1; for i:=l downto 0 do if d[y]-(1<<i)>=d[x] then y:=p[y,i]; end; if x<>y then begin l:=trunc(ln(d[y])/ln(2)); for i:=l downto 0 do if p[x,i]<>p[y,i] then begin x:=p[x,i];y:=p[y,i]; end; x:=p[x,0]; end; exit(x);end;procedure dfs2(x,fa:longint);var k:point;begin siz[x]:=sum[x]; k:=a[x]; while k<>nil do begin if k^.data<>fa then begin dfs2(k^.data,x); inc(siz[x],siz[k^.data]); end; k:=k^.next; end; ans:=max(ans,siz[x]);end;begin readln(n,kk); for i:=1 to n-1 do begin readln(x,y); new(k); k^.data:=y; k^.next:=a[x]; a[x]:=k; new(k); k^.data:=x; k^.next:=a[y]; a[y]:=k; end; dfs(1,0); for i:=1 to kk do begin readln(x,y); fa:=lca(x,y); inc(sum[x]);inc(sum[y]);dec(sum[fa]); if fa<>1 then dec(sum[p[fa,0]]); end; dfs2(1,0); writeln(ans);end.
bzoj4390: [Usaco2015 dec]Max Flow(LCA+树上差分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。