记录编号	355643	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]天天爱跑步	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	4.048 s
提交时间	2016-11-26 16:31:02	内存使用	41.79 MiB

//NOIP2016D1T2
//by Cydiater
//2016.11.26
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <set>
#include <iomanip>
#include <vector>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
#define cmax(a,b)		a=max(a,b)
#define cmin(a,b)		a=min(a,b)
#define Auto(i,node)		for(int i=LINK[node];i;i=e[i].next)
#define FILE "runninga"
const int MAXN=3e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,M,LINK[MAXN],len=0,lable[MAXN],G[MAXN],fa[MAXN],dep[MAXN],dfn[MAXN],Pos[MAXN],dfs_clock,siz[MAXN],cnt1[MAXN<<2],cnt2[MAXN<<2],ans[MAXN];
bool vis[MAXN];
struct edge{
	int y,next;
}e[MAXN<<1];
struct PATH{
	int x,y,lca;
}Path[MAXN];
vector<pii> fri[MAXN],tag1[MAXN],tag2[MAXN],LR[MAXN];
namespace solution{
	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
	inline void Insert(int x,int y){insert(x,y);insert(y,x);}
	int getf(int k){
		if(G[k]==k)	return k;
		G[k]=getf(G[k]);
		return G[k];
	}
	void init(){
		N=read();M=read();
		up(i,2,N){
			int x=read(),y=read();
			Insert(x,y);
		}
		up(i,1,N)lable[i]=read();
		up(i,1,M){
			int x=read(),y=read();
			Path[i].x=x;Path[i].y=y;
			fri[x].push_back(make_pair(i,y));
			fri[y].push_back(make_pair(i,x));
		}
	}
	void Tarjan(int node){
		G[node]=node;vis[node]=1;dfn[node]=++dfs_clock;Pos[dfs_clock]=node;
		siz[node]=1;
		Auto(i,node)if(!vis[e[i].y]){
			dep[e[i].y]=dep[node]+1;
			Tarjan(e[i].y);
			G[e[i].y]=node;fa[e[i].y]=node;
			siz[node]+=siz[e[i].y];
		}
		up(i,0,(int)(fri[node].size()-1))
			if(vis[fri[node][i].second])
				Path[fri[node][i].first].lca=getf(fri[node][i].second);
	}
	void make_tag(int x,int y,int st,bool flag=false){
		if(dep[x]<=dep[y]){
			int fx=fa[x];
			if(fx)tag1[fx].push_back(make_pair(st-dep[x],-1));
			tag1[y].push_back(make_pair(st-dep[x],1));
		}else{
			int fy=fa[y];
			if(flag)	tag2[y].push_back(make_pair(st+dep[x],-1));
			else if(fy)	tag2[fy].push_back(make_pair(st+dep[x],-1));
			tag2[x].push_back(make_pair(st+dep[x],1));
		}
	}
	void slove(){
		Tarjan(1);//O(N+M) LCA and some op
		up(i,1,M){
			int x=Path[i].x,y=Path[i].y,lca=Path[i].lca;
			if(lca==x||lca==y)make_tag(x,y,0);
			else{
				make_tag(x,lca,0,true);
				make_tag(lca,y,dep[x]-dep[lca]);
			}
		}
		up(i,1,N){
			LR[dfn[i]-1].push_back(make_pair(i,-1));
			LR[dfn[i]+siz[i]-1].push_back(make_pair(i,1));
		}
		int Delta=N<<1;
		up(i,1,N){
			int node=Pos[i];
			up(j,0,(int)(tag1[node].size()-1))cnt1[tag1[node][j].first+Delta]+=tag1[node][j].second;
			up(j,0,(int)(tag2[node].size()-1))cnt2[tag2[node][j].first+Delta]+=tag2[node][j].second;
			up(j,0,(int)(LR[i].size()-1)){
				pii tmp=LR[i][j];
				ans[tmp.first]+=cnt1[lable[tmp.first]-dep[tmp.first]+Delta]*tmp.second;
				ans[tmp.first]+=cnt2[lable[tmp.first]+dep[tmp.first]+Delta]*tmp.second;
			}
		}
	}
	void output(){
		up(i,1,N)printf("%d ",ans[i]);
		puts("");
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	init();
	slove();
	output();
	return 0;
}