Description：

给定一棵树，从时刻 $0$ 开始，有若干人从 $S_i$ 出发向 $T_i$ 移动，每单位时刻移动一条边。

对于树上每个点 $x$ ，求 $w_x$ 时刻有多少人恰好路过 $x$ 。

$N,M\le 300000$

Solution：

在 $LCA$ 处将路径断开，在 $LCA$ 的左边，能被观察到的要求是 $d[S_i]-d[x]=w_x$ ，在右边，要求是 $d[x]-d[LCA]+d[S_i]-d[LCA]=w_x$ 。移项，得：

$d[S_i]=d[x]+w_x$ $d[S_i]-2\times d[LCA]=w_x-d[x]$

于是可以利用树上差分的思想，开一个全局的数组，在路径的上端打一个 $-1$ 标记，在下方打一个 $+1$ 标记，那么统计出子树和数组对应位置的值即为答案。具体统计的方法是在走完这个点的所有儿子后，处理这个点的标记，这样数组中的值就是子树和，每次开一个变量记录操作前这个点的值，两值相减就是答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector> 

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010 

struct edge

{

    int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void addedge(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

int w[MAXN];

int s[MAXN],t[MAXN];

int ans[MAXN];

int fa[MAXN],dep[MAXN],top[MAXN],siz[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

    dep[k] = depth;

    siz[k] = 1;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            fa[e[i].to] = k;

            dfs1(e[i].to,depth + 1);

            siz[k] += siz[e[i].to];

            if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

            {

                son[k] = e[i].to;

            }

        }

    }

    return;

}

void dfs2(int k,int tp)

{

    top[k] = tp;

    if(son[k] == 0)return;

    dfs2(son[k],tp);

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k] && e[i].to != son[k])

        {

            dfs2(e[i].to,e[i].to);

        }

    }

    return;

}

int LCA(int a,int b)

{

    while(top[a] != top[b])

    {

        if(dep[top[a]] < dep[top[b]])swap(a,b);

        a = fa[top[a]];

    }

    if(dep[a] > dep[b])swap(a,b);

    return a;

}

void init()

{

    scanf("%d%d",&n,&m);

    int a,b;

    for(int i = 1;i < n;++i)

    {

        scanf("%d%d",&a,&b);

        addedge(a,b);

    }

    for(int i = 1;i <= n;++i)

    {

        scanf("%d",&w[i]);

    }

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d",&s[i],&t[i]);

    }

    memset(ans,0,sizeof(ans));

    return;

}

map<int,int> bucket1,bucket2;

vector<int> add[MAXN];

vector<int> rid[MAXN];

void prepare1()

{

    for(int i = 1;i <= m;++i)

    {

        int k = LCA(s[i],t[i]);

        add[s[i]].push_back(dep[s[i]]);

        rid[fa[k]].push_back(dep[s[i]]);

    }

    return;

}

void check1(int k)

{

    int temp = bucket1[dep[k] + w[k]];

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            check1(e[i].to);

        }

    }

    vector<int>::iterator it;

    for(it = add[k].begin();it != add[k].end();++it)

    {

        ++bucket1[*it];

    }

    for(it = rid[k].begin();it != rid[k].end();++it)

    {

        --bucket1[*it];

    }

    ans[k] += bucket1[dep[k] + w[k]] - temp;

    return;

}

void prepare2()

{

    for(int i = 1;i <= n;++i)

    {

        add[i].clear();rid[i].clear();

    }

    for(int i = 1;i <= m;++i)

    {

        int k = LCA(s[i],t[i]);

        add[t[i]].push_back(dep[s[i]] - 2 * dep[k]);

        rid[k].push_back(dep[s[i]] - 2 * dep[k]);

    }

    return;

}

void check2(int k)

{

    int temp = bucket2[w[k] - dep[k]];

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            check2(e[i].to);

        }

    }

    vector<int>::iterator it;

    for(it = add[k].begin();it != add[k].end();++it)

    {

        ++bucket2[*it];

    }

    for(it = rid[k].begin();it != rid[k].end();++it)

    {

        --bucket2[*it];

    }

    ans[k] += bucket2[w[k] - dep[k]] - temp;

    return;

}

int main()

{

    init();

    dfs1(1,1);

    dfs2(1,1);

    prepare1();

    check1(1);

    prepare2();

    check2(1);

    for(int i = 1;i <= n;++i)

    {

        cout << ans[i] << " ";

    }

    cout << endl;

    return 0;

}