NOIP2016Day1T2-天天爱跑步

2、天天爱跑步

时间限制: 2 Sec  内存限制: 512 MB

题目描述

小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。

《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含n个结点和n−1条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。

现在有m个玩家，第i个玩家的起点为Si，终点为Ti 。每天打卡任务开始时，所有玩家在第0秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点j的 观察员会选择在第Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也正好到达了结点j。小C想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点j作为终点的玩家：若他在第Wj 秒前到达 终点，则在结点j的观察员不能观察到该玩家；若他正好在第Wj 秒到达终点，则在结点j的观察员可以观察到这个玩家。

输入

第一行有两个整数n和m。其中n代表树的结点数量，同时也是观察员的数量，m代表玩家的数量。

接下来n−1行每行两个整数u和v，表示结点u到结点v有一条边。

接下来一行n个整数，其中第j个整数为Wj ，表示结点j出现观察员的时间。

接下来m行，每行两个整数Si和Ti ，表示一个玩家的起点和终点。

对于所有的数据，保证1 ≤ Si , Ti ≤ n ， 0 ≤ Wj ≤ n。

输出

输出1行n个整数，第j个整数表示结点j的观察员可以观察到多少人。

样例输入

6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6



5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5

样例输出

2 0 0 1 1 1


1 2 1 0 1

提示

【样例 1 说明】

对于 1 号点， W1 = 0 ，故只有起点为 1 号点的玩家才会被观察到，所以玩家 1 和玩家 2 被观察到，共 2 人被观察到。

对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。

对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。

对于 4 号点，玩家 1 被观察到，共 1 人被观察到。

对于 5 号点，玩家 1 被观察到，共 1 人被观察到。

对于 6 号点，玩家 3 被观察到，共 1 人被观察到。

【子任务】

每个测试点的数据规模及特点如下表所示。提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。

用了2、3个小时，才把这道题弄出来……

watch[i]表示观察员出现的时间。deep[i]表示节点的深度。
我们可以先用tarjan求出lca。用树上差分统计答案。

然后把每条路径拆成 起点到lca（向上跑）和终点到lca的子节点（向下跑）的两条路径。

对于向上跑的，如果玩家能被观察员i观察到，那么deep[s]-deep[i]=watch[i]   式①

对于向下跑的，就是 deep[s]+deep[i]-2*deep[lca(s,i)]=watch[i]  式②

等号左边是玩家起点与观察者的距离，等号右边是观察者出现时间

向上跑的很显然，向下跑的如何理解？

假设我们知道点a，b到lca（a，b）的距离分别为da，db，那么a，b之间的距离=da+db

但这里的deep不是到lca的距离，是深度，即到根节点的距离+1

deep[s]+deep[i]包含2段信息，1、s到i的距离，   2、lca（s，i）到根节点的距离+1 

第2段包含了2次，所以减去

先看向上跑的

玩家路径：玩家起点 到 起点与终点的lca

将式①移项，deep[s]=deep[i]+watch[i]

发现等号右边是定值

也就是说对与观察者i，他所能观察到的向上跑的玩家，是所有的起点=deep[i]+watch[i]的玩家

换句话说，以i为根的子树中，所有深度为deep[i]+watch[i]的玩家都能被i观察到

我们如果搞一个dfs序，i的在a时入栈，在b时出栈，

那么以i为根的子树就可以转化为区间[a,b]

那么问题就转化为了  在深度为deep[i]+watch[i]的线段树中，查询区间[a,b]的玩家个数

现在就差玩家个数了

很容易想到在起点处+1

但是还要在起点与终点的lca的父节点处-1

差分惯用思想

用sum[]统计这些1和-1的和

那么问题就转化为了  在深度为deep[i]+watch[i]的线段树中，查询区间[a,b]的sum和

提问：为什么是起点处+1，lca的父节点处-1，可以反过来吗？

不可以。

因为起点的深度深，lca的父节点深度浅，在深度深的节点处+1，以深度深度浅的点为根的子树可以包含这个点

想想序列上的差分，是左端点+1，右端点后面的点-1

因为序列差分与前缀和相联系，前面的点的信息对后面的点会产生影响，所以只需加一个1

这里查询的是子树信息，是这个点深度及以下的信息

对照理解即可

向下跑的同理，只简单说怎么做

玩家路径：lca的子节点到玩家终点

把式②移项 deep[s]-2*deep[lca(s,i)]=watch[i]-deep[i]

在watch[i]-deep[i]深度为deep[s]-2*deep[lca(s,i)]的线段树中，终点处+1，lca处-1

查询时查深度为watch[i]-deep[i]的线段树即可

2个小问题：

1、做完向上跑的后，不要忘了清空线段树

2、向下跑的deep[s]-2*deep[lca(s,i)]可能会产生负数，所以全体后移一定长度，root[]数组开大

Code：

var
  n,m,x,y,tot,tot1,tlca,i,j,k:longint; 
  last,lca,last1,father,watch,deep,dis,plca,lalca,ans:array[0..300010] of longint; 
  vis:array[0..300010] of boolean; 
  pre,other,pre1,other1:array[0..600010] of longint; 
  a,b:array[-400005..400005] of longint; 
procedure add(a,b:longint); 
begin
  inc(tot); 
  pre[tot]:=last[a]; 
  last[a]:=tot; 
  other[tot]:=b; 
end; 
procedure add1(a,b:longint); 
begin
  inc(tot1); 
  pre1[tot1]:=last1[a]; 
  last1[a]:=tot1; 
  other1[tot1]:=b; 
end; 
procedure addlca(c:longint); 
begin
  inc(tlca); 
  plca[tlca]:=lalca[c]; 
  lalca[c]:=tlca; 
end; 
function getfather(x:longint):longint;inline; 
begin
  if x=father[x] then exit(x); 
  father[x]:=getfather(father[x]); 
  exit(father[x]); 
end; 
procedure tarjan(x:longint); 
var p,r:longint; 
begin
  vis[x]:=true; 
  p:=last[x]; 
  while p>0 do
  begin
    r:=other[p]; 
    if not vis[r] then
    begin
      deep[r]:=deep[x]+1; 
      tarjan(r); 
      father[r]:=x; 
    end; 
    p:=pre[p]; 
  end; 
  p:=last1[x]; 
  while p>0 do
  begin
    r:=other1[p]; 
    if vis[r] then lca[p>>1]:=getfather(r); 
    p:=pre1[p]; 
  end; 
end; 
procedure dfs(x,sa,sb:longint); 
var p,r:longint; 
begin
  vis[x]:=true; 
  p:=last1[x]; 
  while p>0 do
  begin
    if p and 1=0 then inc(a[deep[x]]) else
      inc(b[dis[p>>1]-deep[x]]); 
    p:=pre1[p]; 
  end; 
  p:=last[x]; 
  while p>0 do
  begin
    r:=other[p]; 
    if not vis[r] then
      dfs(r,a[watch[r]+deep[r]],b[watch[r]-deep[r]]); 
    p:=pre[p]; 
  end; 
  ans[x]:=a[watch[x]+deep[x]]+b[watch[x]-deep[x]]-sa-sb; 
  p:=lalca[x]; 
  while p>0 do
  begin
    dec(a[deep[other1[p<<1 or 1]]]); 
    dec(b[dis[p]-deep[other1[p<<1]]]); 
    if deep[other1[p<<1 or 1]]-deep[x]=watch[x] then dec(ans[x]); 
    p:=plca[p]; 
  end; 
end; 
begin
  readln(n,m); 
  for i:=1 to n-1 do
  begin
    readln(x,y);add(x,y);add(y,x); 
  end; 
  for i:=1 to n do read(watch[i]); 
  readln;tot1:=1; 
  for i:=1 to m do
  begin
    readln(x,y);add1(x,y);add1(y,x); 
  end; 
  for i:=1 to n do father[i]:=i; 
  tarjan(1); 
  for i:=1 to m do
    dis[i]:=deep[other1[i<<1]]+deep[other1[i<<1 or 1]]-deep[lca[i]]*2; 
  for i:=1 to m do addlca(lca[i]); 
  fillchar(vis,sizeof(vis),0); 
  dfs(1,0,0); 
  for i:=1 to n-1 do write(ans[i],' ');writeln(ans[n]);  
end.