蒟蒻求助

55pts

#include<bits/stdc++.h>
#define N 300010
#define M 600010
using namespace std;
int n,m;
int ans[N],w[N],fstr[N];
int bucket1[N<<1],bucket2[N<<1];
struct node{
    int str,end,lca,dis;
}route[N];
struct rec{
    int tot,head[N],to[M],nxt[M];
    int k,d[N],f[N][30];
    void add(int x,int y){to[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
    void pre(){
        queue<int>q;
        d[1]=1;
        f[1][0]=1;
        q.push(1);
        while(q.size()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=nxt[i]){
                if(d[to[i]])continue;
                d[to[i]]=d[x]+1;
                f[to[i]][0]=x;
                for(int j=1;j<=k;j++)f[to[i]][j]=f[f[to[i]][j-1]][j-1];
                q.push(to[i]);
            }
        }
    }
    int lca(int x,int y){
        if(d[x]>d[y])swap(x,y);
        for(int j=k;j>=0;j--)if(d[f[y][j]]>=d[x])y=f[y][j];
        if(x==y)return x;
        for(int j=k;j>=0;j--)if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
        return f[x][0];
    }
}G,Gend,Glca;
void dfs(int x){
    //dis-wx=dend-dx;
    //dis-dend=wx-dx;
    int b1=bucket1[G.d[x]+w[x]],b2=bucket2[w[x]-G.d[x]+N];
    for(int i=G.head[x];i;i=G.nxt[i]){
        if(G.to[i]==G.f[x][0])continue;
        dfs(G.to[i]);
    }
    bucket1[G.d[x]]+=fstr[x];
    for(int i=Gend.head[x];i;i=Gend.nxt[i]){
        int temp=Gend.to[i];
        bucket2[route[temp].dis-G.d[route[temp].end]+N]++;
    }
    ans[x]+=bucket1[G.d[x]+w[x]]-b1+bucket2[w[x]-G.d[x]+N]-b2;
    for(int i=Glca.head[x];i;i=Glca.nxt[i]){
        int temp=Glca.to[i];
        bucket1[G.d[route[temp].str]]--;
        bucket2[route[temp].dis-G.d[route[temp].end]+N]++;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    G.k=(int)(log(n)/log(2.0))+1;
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        G.add(x,y);G.add(y,x);
    }
    G.pre();
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&route[i].str,&route[i].end);
        route[i].lca=G.lca(route[i].str,route[i].end);
        route[i].dis=G.d[route[i].str]+G.d[route[i].end]-2*G.d[route[i].lca];
        fstr[route[i].str]++;
        Gend.add(route[i].end,i);
        Glca.add(route[i].lca,i);
        if(G.d[route[i].lca]+w[route[i].lca]==G.d[route[i].str])ans[route[i].lca]--;
    }
    dfs(1);
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}