CF1076E Vasya and a Tree

Stinger · 2021-07-19 19:49:14 · 题解

如果只是把 u 的 k-son 全部加上 x 就很好做。

大概思路是维护一些vector，第 i 个vector按照dfs序的 \text{In} 值装下所有深度为 i 的节点。然后设 dep_i 为 i 的深度，所有 u 的 k-son 都在第 dep_u+k 个vector中，且 \text{In} 值都在 [\text{In}_u,\text{Out}_u] 中。所以二分查找一下确定 u 的 k-son 在vector中对应的区间，那么把 k-son 加 x 就变成了区间加 x，由于没有修改只有最后输出单点查询，所以我是直接用的差分树状数组，但这里是我nt了，直接差分完全可以。

那如果把 0-son,1-son...k-son 全部加呢？只需要再差分一遍（树上差分）就行了。最后问题变为把 u 点权加上 x，u 的 k+1-son 减去 x。最后统计答案统计树上前缀和就可以了（u 的所有祖先（包括自己）的点权总和）。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define int long long

int c[300005], In[300005], Out[300005], idx[300005], n, cnt;
int s[300005], dep[300005], p[300005];
std::vector<int> G[300005], vec[300005], vec2[300005];
void update(int l, int r, int d) {
    for (int i = l; i <= n; i += (i & ~i + 1)) c[i] += d;
    for (int i = r + 1; i <= n; i += (i & ~i + 1)) c[i] -= d;
}
int query(int x) {
    int sum = 0;
    for (int i = x; i; i -= (i & ~i + 1)) sum += c[i];
    return sum;
}
void dfs(int u, int fa) {
    vec[dep[u] = dep[fa] + 1].push_back(In[u] = ++ cnt);
    vec2[dep[u]].push_back(u);
    for (int v : G[u]) if (v != fa) dfs(v, u);
    Out[u] = cnt;
}
void DFS(int u, int fa) {
    s[u] += query(p[u]);
    for (int v : G[u])
        if (v != fa) s[v] += s[u], DFS(v, u);
}

signed main() {
    scanf("%lld", &n);
    for (int i = 1; i < n; ++ i) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, -1);
    idx[0] = 1;
    for (int i = 1; vec[i].size(); ++ i) {
        idx[i] = idx[i - 1] + vec[i - 1].size();
        for (int j = 0; j < vec[i].size(); ++ j)
            p[vec2[i][j]] = idx[i] + j;
    }
    int m;
    scanf("%lld", &m);
    for (int i = 1; i <= m; ++ i) {
        int x, d, u, k;
        scanf("%lld%lld%lld", &u, &d, &x);
        s[u] += x, k = dep[u] + d + 1;
        if (n < k || !vec[k].size()) continue;
        int st = std::lower_bound(vec[k].begin(), vec[k].end(), In[u]) - vec[k].begin();
        int ed = std::upper_bound(vec[k].begin(), vec[k].end(), Out[u]) - vec[k].begin() - 1;
        update(idx[k] + st, idx[k] + ed, -x);
    }
    DFS(1, -1);
    for (int i = 1; i <= n; ++ i) printf("%lld ", s[i]);
    return 0;
}