C++14(g++5.4) 解法, 执行用时: 559ms, 内存消耗: 101216K, 提交时间: 2020-10-20 15:40:54

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
    rg T data=0,w=1;rg char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
    for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;

co int N=3e5+1;
int n,m,t;
vector<int> e[N];
int fa[N][20],dep[N];
void bfs(){
	t=log(n)/log(2);
	queue<int> q;
	dep[1]=1,q.push(1);
	for(int x;q.size();){
		x=q.front(),q.pop();
		for(int i=0,y;i<e[x].size();++i){
			if(dep[y=e[x][i]]) continue;
			dep[y]=dep[x]+1,fa[y][0]=x;
			for(int j=1;j<=t;++j) fa[y][j]=fa[fa[y][j-1]][j-1];
			q.push(y);
		}
	}
}
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=t;i>=0;--i)
		if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];
	if(x==y) return x;
	for(int i=t;i>=0;--i)
		if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int w[N],c1[N*2],c2[N*2],ans[N];
vector<int> a1[N],b1[N],a2[N],b2[N];
void dfs(int x){
	int val1=c1[dep[x]+w[x]],val2=c2[w[x]-dep[x]+n];
	for(int i=0,y;i<e[x].size();++i)
		if((y=e[x][i])!=fa[x][0]) dfs(y);
	for(int i=0;i<a1[x].size();++i) ++c1[a1[x][i]];
	for(int i=0;i<b1[x].size();++i) --c1[b1[x][i]];
	for(int i=0;i<a2[x].size();++i) ++c2[a2[x][i]+n];
	for(int i=0;i<b2[x].size();++i) --c2[b2[x][i]+n];
	ans[x]=c1[dep[x]+w[x]]-val1+c2[w[x]-dep[x]+n]-val2;
}
int main(){
	read(n),read(m);
	for(int i=1,x,y;i<n;++i){
		read(x),read(y);
		e[x].push_back(y),e[y].push_back(x);
	}
	bfs();
	for(int i=1;i<=n;++i) read(w[i]);
	for(int i=1,x,y,z;i<=m;++i){
		read(x),read(y),z=lca(x,y);
		a1[x].push_back(dep[x]),b1[fa[z][0]].push_back(dep[x]);
		a2[y].push_back(dep[x]-2*dep[z]),b2[z].push_back(dep[x]-2*dep[z]);
	}
	dfs(1);
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 905ms, 内存消耗: 95044K, 提交时间: 2019-11-08 19:35:35

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
int n,m,dep[N],fa[N][25],c1[N],c2[N<<2],ans[N],w[N];
vector<int>g[N],ga1[N],ga2[N],gb1[N],gb2[N];
void dfs(int x,int p)
{
	dep[x]=dep[p]+1;fa[x][0]=p;
	for(int i=0;i<g[x].size();i++)if(g[x][i]!=p)dfs(g[x][i],x);
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	int sub=dep[u]-dep[v];
	for(int i=0;i<=20;i++)if(sub&(1<<i))u=fa[u][i];
	if(u==v)return u;
	for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void chk(int x)
{
	ans[x]=-c1[dep[x]+w[x]]-c2[w[x]-dep[x]+N];
	for(int i=0;i<g[x].size();i++)if(g[x][i]!=fa[x][0])chk(g[x][i]);
	for(int i=0;i<ga1[x].size();i++)c1[ga1[x][i]]++;
	for(int i=0;i<gb1[x].size();i++)c1[gb1[x][i]]--;
	for(int i=0;i<ga2[x].size();i++)c2[ga2[x][i]]++;
	for(int i=0;i<gb2[x].size();i++)c2[gb2[x][i]]--;
	ans[x]+=c1[dep[x]+w[x]]+c2[w[x]-dep[x]+N];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
    {
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	dfs(1,0);
	for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
	for(int i=1;i<=m;i++)
    {
		int u,v;scanf("%d%d",&u,&v);
		int t=lca(u,v);
		ga1[u].push_back(dep[u]);
		gb1[t].push_back(dep[u]);
		ga2[v].push_back(dep[u]-2*dep[t]+N);
		gb2[fa[t][0]].push_back(dep[u]-2*dep[t]+N);
	} 
	chk(1);
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);
	return 0;
}