小众优化trick合订本

做题有时会遇到一些比较少见，但是很巧妙的优化技巧，单独写一篇博客内容又显单薄，索性总结到一篇合集里，不时更新。

重链剖分优化空间

例题：P5391 [Cnoi2019] 青染之心

向序列末尾动态增删物品集合，物品可以无限次选择，问每次操作后可获得的最大价值。

动态完全背包问题，由于刚做完线段树分治，不禁朝这个方向思考，但是数据范围太大，$O(qV\log{q})$ 会T。

仔细观察，发现增删只在末尾出现，满足栈的性质，我们可以把操作离线，抽象成一棵操作树，本质上就是在这棵树上进行dfs遍历。

考虑朴素维护dp数组，自然想到每一层维护一个新版本，进入新层拷贝上层数组后再做dp转移，但这样空间复杂度 $O(qV)$ ，这题空间限制很紧，无法通过。

引入本题的重点：对操作树进行重链剖分，一棵树可以分成 $O(\log{n})$ 条重链，我们让每条重链上的点共享同一个数组空间，这样空间可以限制到 $O(V\log{q})$ ，就可以通过了。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

template<typename T> void chkmin(T& a, T b) { a = min(a, b); }
template<typename T> void chkmax(T& a, T b) { a = max(a, b); }

constexpr int N = 2e4 + 10;
constexpr int MOD = 998244353;

int dp[20][N];
int stk[N], top;
int vis[N], sz[N], son[N];
int v[N], w[N];
int id[N], ans[N];
vector<int> e[N];
int q, V;

void dfs1(int u, int f) {
    vis[u] = 1;
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int f, int cur, int pre) {
    for (int i = 0; i <= V; ++i) {
        dp[cur][i] = dp[pre][i];
        if (i >= w[u]) chkmax(dp[cur][i], dp[cur][i - w[u]] + v[u]);
        chkmax(ans[u], dp[cur][i]);
    }
    for (int v : e[u]) {
        if (v == f || v == son[u]) continue;
        dfs2(v, u, cur + 1, cur);
    }
    if (son[u]) dfs2(son[u], u, cur, cur);
}

void solve() {
    
    cin >> q >> V;
    int n = 0;
    for (int i = 1; i <= q; ++i) {
        string s;
        cin >> s;
        if (s[0] == 'a') {
            ++n;
            cin >> w[n] >> v[n];
            if (top) e[stk[top]].push_back(n);
            stk[++top] = n;
        } else {
            top--;
        }
        if (top) id[i] = stk[top];
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) dfs1(i, 0), dfs2(i, 0, 1, 0);
    }
    for (int i = 1; i <= q; ++i) {
        cout << ans[id[i]] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}