Codeforces 1076E(DFS+离线+线段树)

发表于 | 分类于 | | + s

Codeforces 1076E
题意：$m$次修改，$(v,k,x)$代表将$v$节点之下$k$层的节点全都加$x$，最后统一查询。即输出每个节点的值。

这题没有修改，并且询问只有最后一个，所以考虑离线。
我们发现这题就是子树+层次的题目，那么自然想到 DFS 序 或者 DFS 处理。
层次可以存每层DFS序，但是这样做没什么思路，我们不妨纵向看 (BFS 序相同的为序列的一个元素)
然后对于子树的问题，DFS子树型，即当前 DFS 只处理当前子树。那么这一种修改操作就是修改当前情况下层次序列$[dep,dep+d]$的值，那么我们修改后继续处理子树。然后如果这个子树全部处理完了，那么我们就回退。这些修改回退操作可以写一个区间修改单点查值的数据结构。显然差分 BIT 好写。但是我这里还是脑残写了个线段树。

知识点：
1、层次可以纵向看
2、DFS 可以做到只处理当前子树情况

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 300000 + 5;

    #define lc (o << 1) 
    #define rc (o << 1 | 1)
    #define M ((l + r) >> 1)
    LL sumv[MAXN * 4], lazy[MAXN * 4];

    void pushup(int o) {sumv[o] = sumv[lc] + sumv[rc];}
    void pushdown(int o, int len) {
        if (len == 1) return ;
        if (lazy[o]) {
            lazy[lc] += lazy[o], lazy[rc] += lazy[o];
            sumv[lc] += lazy[o] * (LL)(len - len / 2), sumv[rc] += lazy[o] * (LL)(len / 2);
            lazy[o] = 0;
        }
    }
    void build(int o, int l, int r) {
        if (l == r) return ; sumv[o] = 0;
        build(lc, l, M), build(rc, M + 1, r);
        pushup(o);
    }
    void update(int o, int l, int r, int x, int y, LL v) {
        pushdown(o, r - l + 1);
        if (x <= l && r <= y) {
            sumv[o] += v * (LL)(r - l + 1);
            lazy[o] += v;
            return ;
        }
        if (x <= M) update(lc, l, M, x, y, v);
        if (M < y) update(rc, M + 1, r, x, y, v);
        pushup(o);
    }
    LL query(int o, int l, int r, int p) {
        pushdown(o, r - l + 1);
        if (l == r) return sumv[o];
        if (p <= M) return query(lc, l, M, p);
        else return query(rc, M + 1, r, p);
    }

    int n, m;
    vector<int > G[MAXN];
    vector<pair<int, int > > lx[MAXN];
    LL ans[MAXN];

    void dfs(int u, int fa, int dep) {
        for (int i = 0; i < (int)lx[u].size(); ++i) update(1, 1, n, dep, min(dep + lx[u][i].first, n), (LL)lx[u][i].second);
        ans[u] = query(1, 1, n, dep);
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) dfs(v, u, dep + 1);
        }
        for (int i = 0; i < (int)lx[u].size(); ++i) update(1, 1, n, dep, min(dep + lx[u][i].first, n), (LL)-lx[u][i].second);
    }

    void clean() {
        ms(ans, 0);
    }
    int solve() {
        scanf("%d", &n);
        clean();
        for (int x, y, i = 1; i < n; ++i) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
        build(1, 1, n);
        scanf("%d", &m);
        for (int v, d, x, i = 1; i <= m; ++i) {
            scanf("%d%d%d", &v, &d, &x);
            lx[v].push_back(make_pair(d, x));
        }
        dfs(1, 0, 1);
        for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------