题目链接

题意

三种操作

  1. 在树上加点
  2. 给x号点及其子树所有点加权y
  3. 询问某点权值

思路

因为是动态加点的树难处理，考虑离线。

离线建树。

对子树进行操作，考虑dfs序。

暴力处理为

考虑树状数组进行差分，复杂度降为。

因为点再加上去之前点权为0，所以记录下加点时的点权，询问时再减去即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
class qnode {
   public:
    int op, x, y;
};
void dfs(int now, int& id, vector<vector<int>>& edge, vector<int>& l,
         vector<int>& r) {
    r[now] = l[now] = ++id;
    for (auto& it : edge[now]) {
        dfs(it, id, edge, l, r);
        r[now] = r[it];
    }
}
class BIT {
   public:
    vector<ll> tree;
    int n;
    BIT(int _n) : n(_n), tree(_n + 1, 0) {}
    static int lowbit(int x) { return x & (-x); }
    ll query(int x) {
        ll ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
    void add(int x, ll val) {
        while (x <= n) {
            tree[x] += val;
            x += lowbit(x);
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int q;
    cin >> q;
    vector<qnode> a(q);

    int cnt = 1;
    for (int i = 0; i < q; ++i) {
        cin >> a[i].op >> a[i].x;
        if (a[i].op == 2) cin >> a[i].y;
        cnt += a[i].op == 1;
    }

    vector<vector<int>> edge(cnt, vector<int>());
    for (int i = 0, nowid = 1; i < q; ++i) {
        if (a[i].op == 1) {
            edge[a[i].x].emplace_back(nowid);
            a[i].y = nowid++;
        }
    }

    vector<int> l(cnt), r(cnt);
    int id = 0;
    dfs(0, id, edge, l, r);

    vector<int> del(cnt);
    BIT T(cnt + 1);

    for (int i = 0; i < q; ++i) {
        if (a[i].op == 1) {
            int id = l[a[i].y];
            del[id] = T.query(id);
        }
        if (a[i].op == 2) {
            T.add(l[a[i].x], a[i].y);
            T.add(r[a[i].x] + 1, -a[i].y);
        }
        if (a[i].op == 3) {
            int id = l[a[i].x];
            cout << T.query(id) - del[id] << endl;
        }
    }
    return 0;
}