题目所求可以理解为合法对 $(u,v)$，也即合法的、以 $u,v$ 为端点的路径。可以考虑点分治。

考虑一个分治中心 $R$，对于其范围内的所有点，我们考虑对每个点计算跨过 $R$ 的合法对。

先考虑从 $u$ 向上的路径，分成两类：

• 到达 $R$ 时已经盖过了章。这类点的合法的另一个端点个数只需要简单地计算满足深度 $\le D-dep_u$ 的点的数量即可。
• 到达 $R$ 时还没有盖过章。这类点的计算更为复杂一些。

下面我们考虑第二类点的答案如何计算。

我们对每个点，考虑其作为终点的情况，处理出一个 $t_u$，表示当起点到达 $R$ 的时刻 $\ge t_u$ 时，点 $u$ 可以产生贡献。容易知道一个点的 $t_u$ 可以先从其父亲处继承，再和 $a_u-dep_u$ 取 $\min$。则点 $u$ 可以对到达 $R$ 的时刻在 $[\max(0,t_u),D-dep_u]$ 之间的起点造成贡献。这个可以在树状数组上区间加来维护每种时刻的答案。

做完上面部分的事情后，我们就可以直接计算第二类点的贡献了。注意需要容斥减掉来自同一棵子树的贡献。时间复杂度 $O(n\log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,D,ma[N],siz[N],tot,root,c[N];
vector<int> e[N];int vis[N];
int ty[N],dep[N],t[N],ans[N],a[N],cc,V[N];
struct BIT{
	int t[N];
	void insert(int x,int y){
        V[++cc]=x;
		for(int i=x;i<=n+1;i+=(i&(-i)))
		t[i]+=y;
	}
	int sum(int x){
		int ss=0;
		for(int i=x;i;i-=(i&(-i)))
		ss+=t[i];return ss;
	}
    void clear(int x){
		for(int i=x;i<=n+1;i+=(i&(-i)))
        t[i]=0;
    }
}T;
void undo(){
    for(int i=1;i<=cc;i++)
    T.clear(V[i]);cc=0;
}
void getzx(int u,int fa){
    siz[u]=1;ma[u]=0;
    for(int v:e[u]){
        if(v==fa||vis[v])continue;
        getzx(v,u);siz[u]+=siz[v];
        ma[u]=max(ma[u],siz[v]);
    }
    ma[u]=max(ma[u],tot-siz[u]);
    if(!root||ma[root]>ma[u])root=u;
}
void calc(int u,int fa,int TT,int mi){
    ty[u]=-1;siz[u]=1;
    dep[u]=dep[fa]+1;c[dep[u]]++;
    mi=min(mi,dep[u]+a[u]);
    TT=min(TT,a[u]-dep[u]);
    TT=max(TT,0);t[u]=TT;
    if(dep[u]<=D&&dep[u]<mi)ty[u]=dep[u];
    if(D-dep[u]>=t[u])
    T.insert(t[u]+1,1),T.insert(D-dep[u]+2,-1);
    for(int v:e[u]){
        if(v==fa||vis[v])continue;
        calc(v,u,TT,mi);
        siz[u]+=siz[v];
    }
}
void add(int u,int fa){
    c[dep[u]]++;
    if(D-dep[u]>=t[u])
    T.insert(t[u]+1,1),T.insert(D-dep[u]+2,-1);
    for(int v:e[u]){
        if(v==fa||vis[v])continue;
        add(v,u);
    }
}
void getans(int u,int fa,int op){
    if(ty[u]!=-1)ans[u]+=T.sum(dep[u]+1)*op;
    if(dep[u]<=D&&ty[u]==-1)ans[u]+=op*c[min(D-dep[u],siz[root])];
    for(int v:e[u]){
        if(vis[v]||v==fa)continue;
        getans(v,u,op);
    }
}
void solve(int u){
    vis[u]=1;
    calc(u,0,tot,D+1);
    for(int i=1;i<=siz[u];i++)c[i]+=c[i-1];
    getans(u,0,1);undo();
    for(int i=0;i<=siz[u];i++)c[i]=0;
    for(int v:e[u]){
        if(vis[v])continue;
        add(v,0);
        for(int i=1;i<=siz[v];i++)c[i]+=c[i-1];root=v;
        getans(v,0,-1);
        for(int i=1;i<=siz[v];i++)c[i]=0;
        undo();
    }
    for(int v:e[u]){
        if(vis[v])continue;
        tot=siz[v];root=0;
        getzx(v,0);solve(root);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>D;dep[0]=-1;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }
    tot=n;getzx(1,0);solve(root);
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<'\n';
	return 0;
}