记录编号	356816	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.205 s
提交时间	2016-12-06 19:21:37	内存使用	76.58 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000010;
int n,m,w[N],head[N],tail[N],next[N],T[N],ans[N];
void add(int f,int x){
	if (!head[f]) head[f]=tail[f]=x;
		else tail[f]=next[tail[f]]=x;
}
int fa[N],big[N],h[N],s[N];
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		fa[w[i]]=x;
		h[w[i]]=h[x]+1;
		dfs(w[i]);
		s[x]+=s[w[i]];
		if (s[big[x]]<s[w[i]]) big[x]=w[i];
	}
}
int cnt,dfn[N],link[N];
void dfs1(int x){
	dfn[x]=++cnt;
	link[x]=(dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x);
	if (big[x]){
		dfs1(big[x]);
		for (int i=head[x];i;i=next[i])
		if (w[i]!=big[x]&&w[i]!=fa[x]) dfs1(w[i]);
	}
}
int u[N],v[N],lca[N],l[N];
int LCA(int x,int y){
	while (link[x]!=link[y]){
		if (h[link[x]]<h[link[y]]) swap(x,y);
		x=fa[link[x]];
	}
	return h[x]<h[y]?x:y;
}
struct bit{
	int a[N];
	void add(int p,int d){
		if (!p) return;
		for (;p<=n;p+=(p&-p)) a[p]+=d;
	}
	int sum(int p){
		int ans=0;
		for (;p;p-=(p&-p)) ans+=a[p];
		return ans;
	}
	int sum(int l,int r){
		return sum(r)-sum(l-1);
	}
}Tree;
struct opt{
	int h,k,id;
	opt(int H=0,int K=0,int ID=0){h=H;k=K;id=ID;}
}Q[N];
int p;
bool cmp1(const opt &x,const opt &y){
	if (x.h!=y.h) return x.h<y.h;
	return x.k<y.k;
}
void solve(int *u){
	sort(Q+1,Q+p+1,cmp1);
	for (int i=1;i<=p;){
		int flag=Q[i].h,last=i;
		while (i<=p&&Q[i].h==flag){
			int id=Q[i].id;
			if (!Q[i].k){
				Tree.add(dfn[u[id]],1);
				Tree.add(dfn[fa[lca[id]]],-1);
			}
			else ans[id]+=Tree.sum(dfn[id],dfn[id]+s[id]-1);
			i++;
		}
		for (int j=last;j<i;j++){
			int id=Q[j].id;
			if (!Q[j].k){
				Tree.add(dfn[u[id]],-1);
				Tree.add(dfn[fa[lca[id]]],1);
			}
		}
	}
}
int main()
{
	freopen("runninga.in","r",stdin);
	freopen("runninga.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		scanf("%d%d",&w[i],&w[i+n]);
		add(w[i],i+n);add(w[i+n],i);
	}
	fa[1]=1;dfs(1);dfs1(1);fa[1]=0;
	for (int i=1;i<=n;i++) scanf("%d",&T[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&u[i],&v[i]);
		lca[i]=LCA(u[i],v[i]);
		l[i]=h[u[i]]+h[v[i]]-2*h[lca[i]];
	}
	p=0;
	for (int i=1;i<=n;i++) Q[++p]=opt(h[i]+T[i],1,i);
	for (int i=1;i<=m;i++) Q[++p]=opt(h[u[i]],0,i);
	solve(u);
	p=0;
	for (int i=1;i<=n;i++) Q[++p]=opt(h[i]-T[i],1,i);
	for (int i=1;i<=m;i++) Q[++p]=opt(h[v[i]]-l[i],0,i);
	solve(v);
	for (int i=1;i<=m;i++)
	if (T[lca[i]]==h[u[i]]-h[lca[i]]) ans[lca[i]]--;
	for (int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
	return 0;
}