众所周知noip暴力分暴多

$Case\ 1$

考虑第一个数据点和第二个数据点，显然当且仅当$S_i=T_i=u$时，才会对点$u$产生贡献，因此在标记后线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$10\ pts$

$Case\ 2$

显然当且仅当$u=S_i$时，才会对点$u$产生贡献，标记所有起点线性扫描每个点即可。

复杂度$O(n+m)$

期望得分:$20\ pts$

$Case\ 3$

考虑暴力枚举每条链，对其进行树上差分后依次枚举每个点，该链对点$u$产生贡献当且仅当该点在链上且$dis(S_i,u)=w_u$。

复杂度$O(mn+m\ log\ n)$

期望得分：$25\ pts$

$Case\ 4$

该题退化为链的方式比较特殊。

我们发现，当按所叙述方式退化为链时整个问题转化为线性序列上的问题：

给出一个序列$a$与$m$个区间，求对于序列$a$第$i$个位置前面第$a[i]$个位置上有几个$S_j$满足其对应的$T_j\ge i$。

对于每个位置开一个$vector$，保存其$S_i$恰好为这个位置所对应的所有$T_i$，递增排序后每次二分查找即可。

复杂度$O(n\ log\ n)$

期望得分：$40pts$

$Case\ 5$

当所有的$S_i$为根节点时。

显然当且仅当$T_i$在以$x$为根的子树内时，链$<S_i,T_i>$才会经过$x$。

因此直接$DFS$一遍，统计每个节点到根节点的距离$dis(u)$，如果$dis(u)=w_u$，那么其节点$u$的答案即子树内$T_i$的数量，否则为$0$。

对于$T_i$的数量，直接打标记后$DFS$一遍即可求得。

复杂度$O(n)$

期望得分：$60pts$

$Case\ 6$

我们发现，当终点在根节点时。

其等价于求在以点$u$为根的子树内有多少$S_i$，满足$dis(u,S_i)=w_u$。

我们设点$u$的深度为$deep[u]$，那么即等价于在点$u$的子树内，深度为$deep[u]+w_u$的这一层内有多少$S_i$。

把原树用$DFS$序重编号，按层拆成若干份使用$vector$存储。

对于每个$S_i$对其进行序列单点加之后求前缀和。

在$deep[u]+w_u$这一层的$DFS$序中二分点$u$ $DFS$序所对的区间查询区间和。

复杂度$O(n\ log\ n)$。

期望得分：$80pts$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

namespace wxy{
    const int N = 3e5 + 5,inf = 5e5 + 5;
    int ans[N];
    int head[N],fail[N << 1],edge[N << 1],w[N],tot,n,m;
    int fa[N][35],dep[N],tlca[N],dfn[N],cnt,l[N],r[N];
    bool vis[N];
    int t[N],pt[N],ppt[N],maxdeep;
    typedef std::pair<int,int> PII;
    #define x first
    #define y second
    PII ask[N];
    inline void add(int x,int y){
        edge[++tot] = y;
        fail[tot] = head[x];
        head[x] = tot;
    }
    void dfs1(int x){
        l[x] = ++cnt;
        dfn[cnt] = x;
        for (int i = 1; 1 << i <= n; i++)
            fa[x][i] = fa[fa[x][i-1]][i-1];
        for (int i = head[x];i;i = fail[i]){
            int v = edge[i];
            if (dep[v] != -1) continue;
            fa[v][0] = x;
            dep[v] = dep[x] + 1;
            dfs1(v);
        }
        r[x] = cnt;
    }
    inline int lca(int x,int y){
        if (dep[x] < dep[y]) std::swap(x,y);
        int d = dep[x] - dep[y];
        for (int i = 0; i < 20; i++)
            if (d >> i & 1) x = fa[x][i];
        if (x == y) return x;
        for (int i = 19; i >= 0; i--){
            if (fa[x][i] != fa[y][i]){
                x = fa[x][i];
                y = fa[y][i];
            }
        }
        return fa[x][0];
    }
    inline int get(int x,int y){
        return dep[x] + dep[y] - 2 * dep[lca(x,y)];
    }
    inline void case1(){
        for (int i = 1; i <= m; i++) 
            if (w[ask[i].x] == 0)ans[ask[i].x]++;
    }
    inline void case2(){
        for (int i = 1; i <= m; i++) ans[ask[i].x]++;
    }
    inline void case3(){
        for (int i = 1; i <= m; i++){
            memset(t,0,sizeof t);
            int a = ask[i].x,b = ask[i].y;
            t[a]++;t[b]++;t[tlca[i]]--;
            t[fa[tlca[i]][0]] -= 2;
            for (int j = n; j >= 1; j--) 
                t[fa[dfn[j]][0]] += t[dfn[j]];
            for (int j = 1; j <= n; j++){
                if (t[j] >= 1 && get(j,a) == w[j]){
                    ans[j]++;
                } 
            }
        }
    }
    inline void case4(){
        std::vector<int> pos[N];
        for (int i = 1; i <= n; i++){
            pos[i].push_back(0);
            pos[i].push_back(inf);
        }
        for (int i = 1; i <= m; i++)
            pos[ask[i].x].push_back(ask[i].y);
        for (int i = 1; i <= n; i++)
            std::sort(pos[i].begin(),pos[i].end());
        for (int i = 1; i <= n; i++){
            if (i - w[i] > 0){
                int loc = i - w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] < inf) ans[i] += pos[loc].size() - count - 1;
            }
            if (i + w[i] <= n){
                int loc = i + w[i];
                int count = lower_bound(pos[loc].begin(),pos[loc].end(),i) - pos[loc].begin();
                if (pos[loc][count] > i) count--;
                ans[i] += count;
            }
        }
    }
    inline void case5(){
        for (int i = 1; i <= m; i++)
            pt[ask[i].y]++;
        for (int j = n; j >= 1; j--) 
            pt[fa[dfn[j]][0]] += pt[dfn[j]];
        for (int i = 1; i <= n; i++)
            if (dep[i] == w[i]) ans[i] = pt[i];
    }
    std::vector<int> dfnn[N];
    std::vector<int> ttp[N];
    inline void case6(){
        maxdeep = 0;
        for (int i = 1; i <= n; i++) 
            maxdeep = std::max(maxdeep,dep[i]);
        for (int i = 1; i <= n; i++){
            dfnn[dep[dfn[i]]].push_back(i);
            ttp[dep[dfn[i]]].push_back(0);
        }
        for (int i = 1; i <= m; i++){
            int p = ask[i].x;
            int pos = lower_bound(dfnn[dep[p]].begin(),dfnn[dep[p]].end(),l[p]) - dfnn[dep[p]].begin();
            ttp[dep[p]][pos]++;
        }
        for (int i = 0; i <= maxdeep; i++){
            dfnn[i].push_back(inf);
        }
        for (int i = 0; i <= maxdeep; i++){
            for (int j = 0; j < ttp[i].size(); j++){
                if (j > 0)ttp[i][j] = ttp[i][j - 1] + ttp[i][j];
            }
        }
        for (int i = 1; i <= n; i++){
            if (dep[i] + w[i] > maxdeep) continue;
            int deep = dep[i] + w[i];
            int left = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),l[i]) - dfnn[deep].begin();
            int right = lower_bound(dfnn[deep].begin(),dfnn[deep].end(),r[i]) - dfnn[deep].begin();
            if (dfnn[deep][left] == inf) continue;
            if (dfnn[deep][right] == inf || dfnn[deep][right] > r[i]) right--;
            if (dfnn[deep][left] > r[i] || dfnn[deep][right] < l[i]) continue;
            if (left == 0) ans[i] += ttp[deep][right];
            else ans[i] += ttp[deep][right] - ttp[deep][left - 1];
        }
    }
    void main(){
        cnt = tot = 0;
        std::cin >> n >> m;
        for (int i = 1; i < n; i++){
            int a,b;
            std::cin >> a >> b;
            add(a,b);
            add(b,a);
        }
        memset(dep,-1,sizeof dep);
        dep[1] = 0;
        dfs1(1);
        for (int i = 1; i <= n; i++) std::cin >> w[i];
        for (int i = 1; i <= m; i++){
            std::cin >> ask[i].x >> ask[i].y;
            tlca[i] = lca(ask[i].x,ask[i].y);
        } 
       if (n == 991) case1();
       if (n == 992) case2();
       if (n == 993) case3();
       if (n == 99994) case4();
       if (n == 99995) case5();
       if (n == 99996) case6();
       for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
    }
}signed main(){
    wxy::main();
    return 0;
}