扩散II

普通解法

对于每个查询都用dfs在树上暴力模拟一遍污染
时间复杂度最高可达
空间复杂度

    vector<int> g[200055];
    int a[200005];
    void dfs(int u, int f, int x, int d){
        if(d<0) return;
        a[u] += x;
        for(int v: g[u]) if(v != f) dfs(v, u, x, d-1);
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y, vector<int>& z) {
        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){
            dfs(x[i], 0, z[i], y[i]);
        }
        vector<int> ans; ans.clear();
        for(int i = 1; i <= n; ++i) ans.push_back(a[i]); return ans;
    }

最优解法

首先思考一个简单版本：如果这是一颗有根树，并且每次的操作之后对该结点的距离小于等于的子节点进行操作。因为这个加的操作只和深度有关，所以可以把信息存储起来，利用差分数组，按照深度进行DFS，并在这个过程中修改差分数组的信息来对这些操作进行一个总体的统计。
那么对于该结点，还有它父亲结点方向的满足条件的结点没有加，则相当于对距离父亲结点的子结点进行这个操作，并且因为当前节点已经操作过，所以在这个节点上应该消除父亲节点的贡献。同样，父亲结点的父亲结点的贡献也是如此，那么一直往上爬层就把原本的一个操作分解成了这样的若干个操作。
一个操作最多分解成个操作，所以总的时间复杂度和空间复杂度都为

vector<int> g[200055];
int a[200055], d[200055], dep[200055], fa[200055];
vector<int> val[200055], dis[200055];
void get_fa(int u, int f){
    fa[u] = f; dep[u] = dep[f] + 1;
    for(int v: g[u]) if(v != f) get_fa(v, u); return;
}
void dfs(int u){
    for(int i = 0; i < val[u].size(); ++i){
        d[dep[u]] += val[u][i];
        d[dep[u]+dis[u][i]+1] -= val[u][i];
    }
    a[u] = a[fa[u]] + d[dep[u]];
    for(int v: g[u]) if(v != fa[u]) dfs(v);
    for(int i = 0; i < val[u].size(); ++i){
        d[dep[u]] -= val[u][i];
        d[dep[u]+dis[u][i]+1] += val[u][i];
    }
}
vector<int> solve(int n, int m, vector<int> &u, vector<int>&v, vector<int> &x, vector<int> &y, vector<int> &z){
    for(int i = 0; i <= n; ++i)
        g[i].clear(), val[i].clear(), dis[i].clear(), dep[i] = a[i] = d[i] = 0;
    assert(u.size() == n-1 && v.size() == n-1 && x.size() == m && y.size() == m && z.size() == m);
    for(int i = 0; i < n-1; ++i){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    get_fa(1, 0);
    for(int i = 0; i < m; ++i){
        int cur = x[i];
        int cd = y[i];
        val[cur].push_back(z[i]);
        dis[cur].push_back(cd);
        while(fa[cur] != 0 && cd > 0){
            if(cd > 1) val[cur].push_back(-z[i]), dis[cur].push_back(cd-2);
            cur = fa[cur]; cd--;
            val[cur].push_back(z[i]);
            dis[cur].push_back(cd);
        }
    }
    dfs(1);
    vector<int> ans; ans.clear();
    for(int i = 1; i <= n; ++i) ans.push_back(a[i]); return ans;
}