首页 > 代码库 > 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.
View Code

 

bzoj4390: [Usaco2015 dec]Max Flow(LCA+树上差分)