刚学OI 1e-INF 秒的蒟蒻求助树上差分45pts

RT

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#define mp(a,b) make_pair(a,b)
#define p1(x) x.first
#define p2(x) x.second
#define double long double
#define int long long
using namespace std;
int n;
int m;
int w[300200];
int t1[300200],t3[600200];
int* t2=t3+300100;
int cts[300100];
vector<int>g[300100],cte[300100],ctl[300200];
int fa[300100][21];
int dep[300100];
int s[300100],t[300200],l[300200],len[300200];
inline void dfs(int u){
    dep[u]=dep[fa[u][0]]+1;
    for(int i=1;i<=20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int v:g[u])
        if(v!=fa[u][0]){
            fa[v][0]=u;
            dfs(v);
        }
}
inline int LCA(int u,int v){
    int l=20;
    if(dep[u]<dep[v])swap(u,v);
    while(dep[u]>dep[v]){
        if(dep[fa[u][l]]>=dep[v])
            u=fa[u][l];
        l--;
    }
    if(u==v)return u;
    l=20;
    while(l>=0){
        if(fa[u][l]!=fa[v][l])u=fa[u][l],v=fa[v][l];
        l--;
    }
    return fa[u][0];
}
inline int LEN(int u,int v){
    int l=20;
    int res=0;
       if(dep[u]<dep[v])swap(u,v);
       while(dep[u]>dep[v]){
           if(dep[fa[u][l]]>=dep[v])
               u=fa[u][l],res+=1<<l;
           l--;
       }
       if(u==v)return res;
       l=20;
       while(l>=0){
           if(fa[u][l]!=fa[v][l])u=fa[u][l],v=fa[v][l],res+=1<<l+1;
           l--;
       }
       return res+2;
}
int ans[300200];
inline void calc(int u){
    int s1=t1[dep[u]+w[u]],s2=t2[w[u]-dep[u]];
    for(int v:g[u])
        if(v!=fa[u][0])calc(v);
    t1[dep[u]]+=cts[u];
    for(int i:cte[u])
        t2[len[i]-dep[t[i]]]++;
    ans[u]+=t1[dep[u]-s1+w[u]]+t2[w[u]-dep[u]]-s2;
    for(int i:ctl[u])
        t1[dep[s[i]]]--,t2[len[i]-dep[t[i]]]--;
}
signed main(){
    ios::sync_with_stdio(false);
    freopen("/Users/noip2019/Downloads/P1600_3.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)cin>>w[i];
    dep[0]=-1;
    dfs(1);
    for(int i=1;i<=m;i++){
        cin>>s[i];
        cin>>t[i];
        l[i]=LCA(s[i],t[i]);
        len[i]=LEN(s[i],t[i]);
        ctl[l[i]].push_back(i);
        cts[s[i]]++;
        cte[t[i]].push_back(i);
        if(dep[s[i]]-dep[l[i]]==w[l[i]])ans[l[i]]--;
    }
    calc(1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    return 0;
}