扩散

最优题解

存下每个点可以直接到达的点，形成一棵树。如果我们简单的每次发生提升的直接遍历这个点可以到达的点，那么当每次找的点的度数都很大的时候，会超时。（比如节点1有20000个儿子，节点1发生了100000次提升）
但是我们可以先存下每个节点提升的次数，最后再整个遍历一遍来求出答案。这样每个点只会被父亲访问一次，时间复杂度。因为需要存下每个点可以到达的点，以及预存次数，空间复杂度

vector<int> g[200005];
int a[200005], d[200005];
void dfs(int u, int fa){
    d[u] += a[u]; d[fa] += a[u];
    for(int v: g[u]){
        if(v == fa) continue;
        d[v] += a[u];
        dfs(v, u);
    }
    return;
}
vector<int> solve(int n, int m, vector<int> &u, vector<int>&v, vector<int> &q){
    for(int i = 0; i <= n; ++i) g[i].clear(), a[i] = d[i] = 0;
    assert(u.size() == n-1 && v.size() == n-1 && q.size() == m);
    for(int i = 0; i < n-1; ++i){
        g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]);
    }
    for(int i = 0; i < m; ++i){
        a[q[i]] ++;
    }
    dfs(1, 0);
    vector<int> ans; ans.clear();
    for(int i = 1; i <= n; ++i) ans.push_back(d[i]); return ans;
}