CF1891F A Growing Tree 题解

Iniaugoty · 2023-11-27 22:47:46 · 题解

啊？这么简单的题，Div.2F，*2000？

动态加点是不好搞的，考虑把操作离线下来，先把树建好。然后因为是对子树操作的，子树这种东西在 dfs 序上是连续的，再把树挂到 dfs 序上。

发现正着不太好搞，不断加点使得子树对应区间不好确定，那就倒着搞。操作 2 就是区间加；操作 1 时，某个结点才刚被加入，所有对它权值有影响的操作 2 都在它后面已经被执行过了，所以此时这个点的值就是最终它的值（即答案）。

区间修改单点查询，经典树状数组维护差分数组。

时间复杂度 \mathcal O (q \log n)，空间复杂度 \mathcal O (n)。

#include <bits/stdc++.h>

#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 5e5 + 5;

int _, q, n;
int op[N], x[N], y[N];
vector<int> e[N];
void Addedge(int u, int v) {
    e[u].push_back(v);
    return ;
}

int cnt, dfn[N], siz[N];
void Dfs(int u) {
    dfn[u] = ++cnt;
    siz[u] = 1;
    for (auto v : e[u])
        Dfs(v), siz[u] += siz[v];
    return ;
}

LL t[N];
int lowbit(int x) { return x & -x; }
void Update(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i))
        t[i] += k;
    return ;
}
LL Query(int x) {
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += t[i];
    return res;
}

LL ans[N];

int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> _;
    while (_--) {
        cin >> q, n = 1;
        F(i, 1, q) {
            cin >> op[i] >> x[i];
            if (op[i] == 1) Addedge(x[i], y[i] = ++n);
            else cin >> y[i];
        }
        Dfs(1);
        dF(i, q, 1)
            if (op[i] == 1) ans[y[i]] = Query(dfn[y[i]]);
            else
                Update(dfn[x[i]], y[i]),
                Update(dfn[x[i]] + siz[x[i]], -y[i]);
        ans[1] = Query(1);
        F(i, 1, n) cout << ans[i] << " ";
        cout << "\n";
        F(i, 1, n) t[i] = 0, e[i].clear();
        cnt = 0;
    }
    return 0;
}