Description
这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。现在有个玩家,第个玩家的起点为Si ,终点为Ti 。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点的观察员会选择在第Wj秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也理到达了结点J 。 小C想知道每个观察员会观察到多少人?注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点J作为终点的玩家: 若他在第Wj秒重到达终点,则在结点J的观察员不能观察到该玩家;若他正好在第Wj秒到达终点,则在结点的观察员可以观察到这个玩家。 n,m<=300000
NOI P! 2016 D1T2天天爱跑步 初见时我还是一只图都不会存的弱菜，而现在已经是一只会存图的弱菜了。不禁感叹起那似水流年。。。（我一定是中毒了！）
首先将每条s->t的路径剖开，设s,t的lca为anc。那么就变成了链条路径，设观察节点为x，分开考虑2条链：
s->anc 当deep[s]-deep[x]==w[x]即deep[x]+w[x]==deep[s]的时候可以观察到。
t->anc 当deep[t]-(deep[s]+deep[t]-2*deep[anc]==deep[i]-w[i])的时候可以观察到。
还有个条件就是s,t必须在x的子树里，而anc不在x的子树里。
将所有的s和t差分扔到树上，在anc的位置删除。之后dfs枚举节点的子树，在dfs的时候对每个节点统计答案。维护两个桶，一个记录s，一个记录t，统计子树的答案。
时间复杂度lca: O(nlogn) dfs: O(n+m)
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 301000
inline void read(int &x)
{
char ch=getchar(); x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y) {to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;}
int n,m,deep[N],in[N],tot,lca[N<<1][20],Log[N<<1],bin[20],w[N],ans[N];
vector<int>si[N],ti[N],sd[N],td[N];
int ts[N<<1],tt[N<<1];
void dfs1(int x,int pre)
{
in[x]=++tot; lca[tot][0]=x; deep[x]=deep[pre]+1;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs1(to[i],x),lca[++tot][0]=x;
}
void dfs2(int x,int pre)
{
int tmp1=ts[deep[x]+w[x]],tmp2=tt[deep[x]-w[x]+n];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs2(to[i],x);
for(int i=0;i<si[x].size();++i) ts[si[x][i]]++;
for(int i=0;i<ti[x].size();++i) tt[ti[x][i]]++;
for(int i=0;i<sd[x].size();++i) ts[sd[x][i]]--;
for(int i=0;i<td[x].size();++i) tt[td[x][i]]--;
ans[x]+=(ts[deep[x]+w[x]]+tt[deep[x]-w[x]+n]-tmp1-tmp2);
}
int get_lca(int x,int y)
{
if(in[x]>in[y]) swap(x,y);
int tmp=Log[in[y]-in[x]+1];
return deep[ lca[ in[x] ][tmp] ] < deep[ lca[ in[y]-bin[tmp]+1 ][tmp] ] ?
lca[ in[x] ][tmp] : lca[ in[y]-bin[tmp]+1 ][tmp];
}
int main()
{
read(n); read(m); int x,y;
for(int i=1;i<n;++i)
{
read(x); read(y);
add(x,y); add(y,x);
}
dfs1(1,0);
for(int i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
for(int i=0;i<=Log[tot];++i) bin[i]=1<<i;
for(int i=1;i<=Log[tot];++i)
for(int j=1;j+bin[i-1]<=tot;++j)
lca[j][i]= deep[lca[j][i-1]] < deep[lca[j+bin[i-1]][i-1]] ? lca[j][i-1] : lca[j+bin[i-1]][i-1];
for(int i=1;i<=n;++i) read(w[i]);
int anc,tmp;
while(m--)
{
read(x); read(y); anc=get_lca(x,y);
if(deep[x]-deep[anc]==w[anc]) ans[anc]++;
si[x].push_back(deep[x]); sd[anc].push_back(deep[x]);
tmp=n-deep[x]+2*deep[anc]; ti[y].push_back(tmp); td[anc].push_back(tmp);
}
dfs2(1,0); printf("%d",ans[1]);
for(int i=2;i<=n;++i) printf(" %d",ans[i]);
return 0;
}