CF1891F

标签：int auto void dfs CF1891F tot 节点

Div 2F 放这个，有点奇异搞笑了。

不难发现一个节点的权值完全取决于他所有祖先节点在这个节点放置之后的操作。

通过 dfs，我们可以维护从根节点到当前节点这条链的所有操作，我们只关心在这个节点放置后的操作，于是在操作二时可以这样：在某个数组中第 \(sz\) 个位置加上 \(v\)。那么这个节点的答案就是从当前这个节点的编号开始一直到数组最后的所有元素的和。

树状数组维护单点修，前缀和即可。

int q, tot;
LL c[N];
void modify(int x, int v) {
    for(; x <= q; x += x & -x) {
        c[x] += v;
    }
}

LL query(int x) {
    LL res = 0;
    for(; x; x -= x & -x) {
        res += c[x];
    }
    return res;
}

vector<int> e[N];
vector<PII> g[N];
LL ans[N];

void dfs(int u) {
    for(auto k : g[u]) {
        modify(k.se, k.fi);
    }
    ans[u] = query(q) - query(u - 1);
    for(auto v : e[u]) {
        dfs(v);
    }
    for(auto k : g[u]) {
        modify(k.se, -k.fi);
    }
}

void solve() {
    tot = 1;
    cin >> q;
    for(int i = 1; i <= q; i ++) {
        e[i].clear();
        g[i].clear(); 
        ans[i] = 0;
        c[i] = 0;
    }
    for(int i = 1; i <= q; i ++) {
        int op, x, v;
        cin >> op >> x;
        if(op == 1) {
            tot ++;
            e[x].push_back(tot);
        }
        else {
            cin >> v;
            g[x].push_back({v, tot});
        }
    }
    dfs(1);
    for(int i = 1; i <= tot; i ++) {
        cout << ans[i] << " \n"[i == tot];
    }
}

标签：int,auto,void,dfs,CF1891F,tot,节点
From： https://www.cnblogs.com/Svemit/p/17993638