P5391 [Cnoi2019]青染之心
Solution
把每次（add）询问看成一个节点，原问题相当于以 dfs 序给定一棵树，对每个节点求其到根的一条链上做一遍完全背包的答案。
考虑直接树形转移，时间复杂度为 \(O(qV)\)，可以接受。但空间复杂度就不行了。
最无脑的 dp 设计就是对每个点开 \(O(V)\) 的空间。思考是否可以循环利用 dp 状态，不妨按深度处理，遍历一个深度为 \(d\) 节点的每棵子树时，把 \(d + 1\) 的 dp 值用深度为 \(d\) 的 dp 值覆盖即可。
但是极端情况如链还是会炸。上重链剖分，对一个点 \(u\)，先所有遍历轻儿子，按上述方法处理；最后遍历重儿子，因为只剩一个子节点了，之后不会再用到 \(u\) 处的 dp 值去覆盖其他点，所以深度不用加一，让 \(u\) 的重儿子直接继承 \(u\) 的 dp 值并覆盖 \(u\) 处深度为 \(d\) 的 dp 值。此时的 \(d\) 不再表示深度，倒不如说是一个节点位于从上往下的第几条链。
由熟知的结论，重链剖分后，一条路径被分成 \(O(\log{n})\) 条链，因此深度由跳链的转移最多增加到 \(O(\log{n})\) 数量级，此时时间复杂度仍为 \(O(qV)\)，空间复杂度降为 \(O(V\log{q})\)。
注意有可能删空了会形成森林。
#include<bits/stdc++.h>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
const int N = 2e4 + 5;
const int F = 21;
int n, Q, V, q[N];
int f[F][N], ans[N];
struct Iowa
{
int vis;
int x, y;
int sz, fath, son;
}iw[N];
struct Eugen
{
int stk[N], tp;
void clear() { tp = 0; }
bool empty() { return !tp; }
void push(int x) { stk[++tp] = x; }
void pop() { tp--; }
int top() { return stk[tp]; }
int size() { return tp; }
}css;
struct Lexington
{
int e, ne;
};
struct Sakawa
{
int idx, h[N];
Lexington lxt[N << 1];
void add(int a, int b)
{
lxt[++idx] = (Lexington){b, h[a]};
h[a] = idx;
}
void adds(int a, int b)
{
add(a, b), add(b, a);
}
void dfs1(int u, int fa)
{
iw[u].sz = 1;
iw[u].vis = 1;
iw[u].fath = fa;
for(int i = h[u]; i; i = lxt[i].ne)
{
int v = lxt[i].e;
if(v == fa)
continue;
dfs1(v, u);
iw[u].sz += iw[v].sz;
if(iw[v].sz > iw[iw[u].son].sz)
iw[u].son = v;
}
}
void dfs2(int u, int d, int op)
{
if(op) for(int i = 0; i <= V; ++i) f[d][i] = f[d - 1][i];
for(int i = iw[u].x; i <= V; ++i) chkmx(f[d][i], f[d][i - iw[u].x] + iw[u].y);
for(int i = 0; i <= V; ++i) chkmx(ans[u], f[d][i]);
for(int i = h[u]; i; i = lxt[i].ne)
{
int v = lxt[i].e;
if(v == iw[u].fath || v == iw[u].son)
continue;
dfs2(v, d + 1, 1);
}
if(iw[u].son) dfs2(iw[u].son, d, 0);
}
}skw;
int main()
{
scanf("%d %d", &Q, &V);
for(int i = 1; i <= Q; ++i)
{
char ch[5];
scanf("%s", ch);
if(ch[0] == 'a')
{
++n;
q[i] = n;
scanf("%d %d", &iw[n].x, &iw[n].y);
if(!css.empty())
skw.adds(css.top(), n);
css.push(n);
}
else
{
css.pop();
if(!css.empty())
q[i] = css.top();
}
}
for(int i = 1; i <= n; ++i)
if(!iw[i].vis)
{
skw.dfs1(i, 0);
skw.dfs2(i, 1, 1);
}
for(int i = 1; i <= Q; ++i)
printf("%d\n", ans[q[i]]);
return 0;
}