【NOIP2016】天天爱跑步（树上差分）

题意：

小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。?天天爱跑步?是一个养成类游戏,需要

玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两

个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的

起点为Si ,终点为Ti 。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度,

不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以

每个人的路径是唯一的)小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。在结点的观察员会选

择在第Wj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J 。小C想知道

每个观察员会观察到多少人?注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一段时

间后再被观察员观察到。即对于把结点J作为终点的玩家: 若他在第Wj秒重到达终点,则在结点J的观察员不能观察

到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。

思路：From http://blog.csdn.net/doyouseeman/article/details/53385565

我们思考一下从x到y的路径，
这个可以拆成从x到lca的路径和从lca到y的路径，这个很明显。
如果一个点i在从x到lca 的路径可以检测到的话，
那么就有deep[i]+w[i]=deep[x]。
如果一个点i在从lca到y的路径上可以检测到的话，
那么就有deep[i]-w[i]=deep[y]-t（t表示x到y的路径长度）。
那么用树链剖分的方法很容易，但是很慢。有一个用桶的方法，跑得很快。
维护两个桶，一个向上的桶a和一个向下的桶b。
从x到y的一个路径，在x中a[deep[x]]加一个，当dfs把lca退栈的时候，x的影响就没有了，那么把a[deep[x]]减掉。
在lca那里需要把一个b[deep[y]]加进来，在y出栈后，就把b[deep[y]]减掉。
每次ans[x]的答案就是子树a[deep[x]+w[x]]+b[deep[x]-w[x]]的数量。
但是如果是一条链的情况，那么这样会算重，所以还要减去重复的数量。

 var shang,xia:array[-..]of longint;

     head,head1,head2,head3:array[..]of longint;

     vet,vet1,vet2,vet3,

     next,next1,next2,next3,ans,dep,a,s:array[..]of longint;

     f:array[..,..]of longint;

     n,m,i,x,y,q,b,tot,tot1,tot2,tot3,t:longint;

 procedure add(a,b:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  head[a]:=tot;

 end;

 procedure add1(a,b:longint);

 begin

  inc(tot1);

  next1[tot1]:=head1[a];

  vet1[tot1]:=b;

  head1[a]:=tot1;

 end;

 procedure add2(a,b:longint);

 begin

  inc(tot2);

  next2[tot2]:=head2[a];

  vet2[tot2]:=b;

  head2[a]:=tot2;

 end;

 procedure add3(a,b:longint);

 begin

  inc(tot3);

  next3[tot3]:=head3[a];

  vet3[tot3]:=b;

  head3[a]:=tot3;

 end;

 procedure dfs(u,fa:longint);

 var e,v,i:longint;

 begin

  for i:= to  do

  begin

   if dep[u]<(<<i) then break;

   f[u,i]:=f[f[u,i-],i-];

  end;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    f[v,]:=u;

    dep[v]:=dep[u]+;

    dfs(v,u);

   end;

   e:=next[e];

  end;

 end;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 function lca(x,y:longint):longint;

 var i,d:longint;

 begin

  if dep[x]<dep[y] then swap(x,y);

  d:=dep[x]-dep[y];

  for i:= to  do

   if d and (<<i)> then x:=f[x,i];

  for i:= downto  do

   if f[x,i]<>f[y,i] then

   begin

    x:=f[x,i]; y:=f[y,i];

   end;

  if x=y then exit(x);

  exit(f[x,]);

 end;

 procedure dfs1(u,fa:longint);

 var e,v,x,y:longint;

 begin

  x:=xia[dep[u]+a[u]];

  y:=shang[dep[u]-a[u]];

  xia[dep[u]]:=xia[dep[u]]+s[u];

  e:=head1[u];

  while e<> do

  begin

   v:=vet1[e];

   inc(shang[v]);

   e:=next1[e];

  end;

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then dfs1(v,u);

   e:=next[e];

  end;

  ans[u]:=xia[dep[u]+a[u]]+shang[dep[u]-a[u]]-x-y;

  e:=head2[u];

  while e<> do

  begin

   v:=vet2[e];

   dec(xia[v]);

   if v=dep[u]+a[u] then dec(ans[u]);

   e:=next2[e];

  end;

  e:=head3[u];

  while e<> do

  begin

   v:=vet3[e];

   dec(shang[v]);

   e:=next3[e];

  end;

 end;

 begin

  assign(input,'bzoj4719.in'); reset(input);

  assign(output,'bzoj4719.out'); rewrite(output);

  readln(n,m);

  for i:= to n- do

  begin

   readln(x,y);

   add(x,y); add(y,x);

  end;

  dfs(,);

  for i:= to n do read(a[i]);

  for i:= to m do

  begin

   readln(x,y);

   q:=lca(x,y);

   t:=dep[x]+dep[y]-*dep[q];

   inc(s[x]); b:=dep[y]-t;

   add1(y,b);

   add2(q,dep[x]);

   add3(q,b);

  end;

  dfs1(,);

  for i:= to n- do write(ans[i],' ');

  write(ans[n]);

  close(input);

  close(output);

 end.

巴特西

【NOIP2016】天天爱跑步（树上差分）

最新文章

热门文章