meaning of the title

Title Link

Sol

Think step by step

\(25 \% \): direct \ (O(nm) \) violence

Chain case: maintain two differential arrays, representing left to right and right to left contributions respectively,

\(S_i = 1 \): count the number of starting points in the subtree of each point

\(T_i = 1 \): it is also the idea of difference. Since the depth of each point to be generated is the same (assuming \ (x \)), record the number of \ (dep[x] \) when accessing the point, and then make a difference between the number of \ (dep[x] \) at the end

The full score method is similar to the above. We consider to convert the contribution of each point to the subtree statistics

For each inquiry, there are two types (from bottom to top / from top to bottom) of \ (s - > LCA, LCA - > t \)

Conditions to be met from top to bottom: \ (dep[i] - w[i] = dep[T] - len \)

Conditions to be met from bottom to top: \ (dep[i] + w[i] = dep[s] \)

#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP make_pair
#define fi first
#define se second 
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7, B = 20;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, ans[MAXN], dep[MAXN], top[MAXN], son[MAXN], siz[MAXN], fa[MAXN], S[MAXN], 
          T[MAXN], w[MAXN], tmp[MAXN], num2[MAXN], sum1[MAXN], sum2[MAXN], Lca[MAXN];
int *num1;//Up > below 
vector<int> up[MAXN], da[MAXN], dc[MAXN];
vector<int> v[MAXN];
void dfs(int x, int _fa) {
    dep[x] = dep[_fa] + 1; siz[x] = 1; fa[x] = _fa;
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == _fa) continue;
        dfs(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(int i = 0, to; i < v[x].size(); i++) 
        if(!top[to = v[x][i]]) dfs2(to, to);
}
int LCA(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
void Deal(int s, int t, int id) {// from s to t
    int lca = LCA(s, t); Lca[id] = lca;
    up[lca].push_back(s);//from down to up
    int dis = dep[s] + dep[t] - 2 * dep[lca];
    sum2[s]++;
    da[t].push_back(dep[t] - dis);//increase
    dc[lca].push_back(dep[t] - dis);//decrase
}
void Find(int x) {
    int t1 = num1[dep[x] - w[x]], t2 = num2[dep[x] + w[x]];// 1: from top to bottom 2: from bottom to top 
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == fa[x]) continue;
        Find(to);
    }
    num2[dep[x]] += sum2[x];
    for(int i = 0; i < da[x].size(); i++) num1[da[x][i]]++;
    ans[x] += num2[dep[x] + w[x]] - t2 + num1[dep[x] - w[x]] - t1;
    for(int i = 0; i < up[x].size(); i++) num2[dep[up[x][i]]]--;
    for(int i = 0; i < dc[x].size(); i++) num1[dc[x][i]]--;
}
int main() {
    //freopen("a.in", "r", stdin); freopen("a.out", "w", stdout);
    num1 = tmp + (int)3e5 + 10;
    N = read(); M = read();
    for(int i = 1; i <= N - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    dep[0] = -1; dfs(1, 0); dfs2(1, 1);
    //for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= N; j++) printf("%d %d %d\n", i, j, LCA(i, j));  
    for(int i = 1; i <= N; i++) w[i] = read();
    for(int i = 1; i <= M; i++) S[i] = read(), T[i] = read(), Deal(S[i], T[i], i);
    Find(1);
    for(int i = 1; i <= M; i++) if(dep[S[i]] - dep[Lca[i]] == w[Lca[i]]) ans[Lca[i]]--;
    for(int i = 1; i <= N; i++) printf("%d ", ans[i]);
    return 0;
}