题解：P5391 [Cnoi2019] 青染之心

前几篇重链剖分题解中都说或者用到了一个结论：重链剖分最多把一棵树剖分成 条链。

那我问你，如果我祭出这张图，阁下如何应对？

这个结论是错误的。而且影响很大，考场上全 一个明明可以切的题目是划不来的。仅仅是这道题目的数据允许了这样的通过。巧合而已。

因为每个叶子节点与每条链一一映射，链的数量是和叶子节点数量持平的，而最多为 的级别（树仅仅只有根节点和叶结点）。如果是这样，那么空间复杂度又会超标。怎么办？

可以发现对于递推数组 的使用在某一个重链递归退出后就不再使用了，因为答案已经计算出来。也就是说，每时每刻一定需要维护的 数组个数，也就是根到叶子节点经过的链数。所以如果可以动态地申请使用 数组的空间，就可以保证 ，而这个是 vector 可以做到的。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 20005;

int q, v, ind = 0;
string s;
int cost[MAXN], val[MAXN];

int vis[MAXN];
int edgeCount;
int head[MAXN], toNode[MAXN], nextEdge[MAXN];
int siz[MAXN], son[MAXN];

vector< vector<int> > f;
int ans[MAXN];
vector< pair<int, int> > era;

inline void addEdge(int from, int to) {
    edgeCount++;
    toNode[edgeCount] = to;
    nextEdge[edgeCount] = head[from];
    head[from] = edgeCount;
    return;
}

inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

inline void dfs1(int from, int father) {
    siz[from]++;
    for (int i = head[from]; i; i = nextEdge[i]) {
        int to = toNode[i];
        if (to != father) {
            dfs1(to, from);
            siz[from] += siz[to];
            if (siz[son[from]] < siz[to])
                son[from] = to;
        }
    }
    return;
}
inline void dfs2(int from, int father) {
    for (int j = cost[from]; j <= v; ++j)
        f.back()[j] = max(f.back()[j], f.back()[j - cost[from]] + val[from]);
    ans[from] = f.back()[v];
    for (int i = head[from]; i; i = nextEdge[i]) {
        int to = toNode[i];
        if (to != father && to != son[from]) {
            f.push_back(f.back());
            dfs2(to, from);
            f.pop_back();
        }
    }
    if (son[from])
        dfs2(son[from], from);
    return;
}

int main() {
    q = read(), v = read();
    f.push_back(vector<int>(v + 1, 0));
    vis[0] = 20001;
    for (int i = 1; i <= q; ++i) {
        cin >> s;
        if (s[0] == 'a') {
            addEdge(vis[ind], i);
            vis[++ind] = i;
            cost[i] = read(), val[i] = read();
        } else
            --ind, era.push_back({i, vis[ind]});
    }
    dfs1(vis[0], 0);
    dfs2(vis[0], 0);
    for (auto i : era)
        ans[i.first] = ans[i.second];
    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
    return 0;
}

花絮：

1. 本来想要卡常卡进最优解的，结果偶遇知识型问题，拼尽全力无法战胜，vector 常数直接破碎了这个想法。
2. dfs2 函数中使用参数 用于记录经过的重链个数，就可以搭配数组使用，因为进行了重复利用，而不是对于每一个子链进行重新分配。
   （详情可以见我的最优解，就是滚动数组重复利用实现的）
3. 用 vector 一定要先初始化不为 empty，否则取出 .back() 的时候就老实了。
4. 如果根节点是 的话， 一定要进行非 初始化。