NOIP2016 天天爱跑步

一道综合性非常强的好题
最朴素的做法，便是模拟：模拟某一个玩家的移动（假设是从u跑到v,那么求出u与v的LCA w，然后考察u->w与v->w上的点即可)，在到达某个节点时判断能否被这个点上的观察员观察到。
这样做肯定是会t的，不过会为我们提供一个思路:
假设出发时间是st_u，并且j是从u->v路径上的一个节点，那么如果有st_u+dis(u,j)==W[j]，这个u->的玩家便会对j产生贡献
dis(u,j)怎么计算呢？用LCA,u,j的dep进行计算就可以了。
为了方便讨论，我们把路径分为向上的路径和向下的路径；对于u->lca->v的路径，只需要拆成u->w和w->v即可。
开始大力推式子：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=3e5+5;
const int D=6e5;

int N,M;
int Dep[MAXN],lg2[MAXN],W[MAXN],Ans[MAXN];
int Fa[MAXN][20];
int Bac_Up[MAXN<<3],Bac_Down[MAXN<<3];
vector<int>G[MAXN];
vector<int>Up_st[MAXN],Up_ed[MAXN],Down_st[MAXN],Down_ed[MAXN];

void Prepare(int cur,int pre) {
	Dep[cur]=Dep[pre]+1;
	Fa[cur][0]=pre;
	for(int k=1; k<=lg2[Dep[cur]]; k++)
		Fa[cur][k]=Fa[Fa[cur][k-1]][k-1];
	for(int i=0; i<G[cur].size(); i++) {
		int ver=G[cur][i];
		if(ver==pre)
			continue;
		Prepare(ver,cur);
	}
}

int LCA(int u,int v) {
	if(Dep[u]<Dep[v])
		swap(u,v);
	while(Dep[u]>Dep[v])
		u=Fa[u][lg2[Dep[u]-Dep[v]]];
	if(u==v)
		return u;
	for(int k=lg2[Dep[u]]; k>=0; k--)
		if(Fa[u][k]!=Fa[v][k])
			u=Fa[u][k],v=Fa[v][k];
	return Fa[u][0];
}

void Dfs_Up(int cur,int pre) {
	int tmp=Bac_Up[W[cur]+Dep[cur]];
	for(int i=0; i<G[cur].size(); i++) {
		int ver=G[cur][i];
		if(ver==pre)
			continue;
		Dfs_Up(ver,cur);
	}
	for(int i=0; i<Up_st[cur].size(); i++)
		Bac_Up[Up_st[cur][i]]++;
	Ans[cur]+=Bac_Up[W[cur]+Dep[cur]]-tmp;
	for(int i=0; i<Up_ed[cur].size(); i++)
		Bac_Up[Up_ed[cur][i]]--;
}

void Dfs_Down(int cur,int pre) {
	for(int i=0; i<Down_st[cur].size(); i++)
		Bac_Down[Down_st[cur][i]+D]++;
	//start from this pos to go down the tree
	int tmp=Bac_Down[W[cur]-Dep[cur]+D];
	for(int i=0; i<Down_ed[cur].size(); i++)
		Bac_Down[Down_ed[cur][i]+D]--;
	for(int i=0; i<G[cur].size(); i++) {
		int ver=G[cur][i];
		if(ver==pre)
			continue;
		Dfs_Down(ver,cur);
	}
	//minus the roads end in the subtree to calclulate the answer
	Ans[cur]+=tmp-Bac_Down[W[cur]-Dep[cur]+D];
}

int main() {
	//freopen("in.txt","r",stdin);
	//freopen("ou.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin>>N>>M;
	for(int i=2; i<=N; i++)
		lg2[i]=lg2[i>>1]+1;
	for(int i=1,u,v; i<N; i++) {
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	Prepare(1,0);
	for(int i=1; i<=N; i++)
		cin>>W[i];
	//for(int i=1;i<=N;i++)
	//	cout<<W[i]<<" ";
	//cout<<endl;
	for(int i=1,s,t; i<=M; i++) {
		cin>>s>>t;
		//++Ans[s];
		int w=LCA(s,t);
		if(w!=s&&w!=t) {
			Up_st[s].push_back(Dep[s]);
			Up_ed[w].push_back(Dep[s]);
			Down_st[w].push_back(Dep[s]-2*Dep[w]);
			Down_ed[t].push_back(Dep[s]-2*Dep[w]);
			if(W[w]==Dep[s]-Dep[w])
				--Ans[w];
		} else if(s==w) {
			Down_st[s].push_back(-Dep[s]);
			Down_ed[t].push_back(-Dep[s]);
		} else {
			Up_st[s].push_back(Dep[s]);
			Up_ed[t].push_back(Dep[s]);
		}
	}
	Dfs_Up(1,0);
	Dfs_Down(1,0);
	for(int i=1; i<=N; i++)
		cout<<Ans[i]<<' ';
	return 0;
}