在同是长链剖分 DP 的 CF1009F 的 OI Wiki 题解中,是这么按 dfs 序开空间的:
void dfs2(int x) {
dfn[x] = ++tim;
f[x] = DP + dfn[x];
son[x] && (dfs2(son[x]), 0);
for (reg int i = head[x], v; i; i = eg[i].nxt)
dfn[v = eg[i].v] || (dfs2(v), 0);
}
void dp(int x) {DP过程略}
在此题的题解中,各种乱七八糟的开空间方法:
int len = height[to] - dep[to] + 1;
f[to] = posf;
posf += len;
posg += len * 2 + 10;
g[to] = posg;
f[y] = o, o += dep[y] << 1, g[y] = o, o += dep[y] << 1;
- 这几种开空间的方式有什么区别吗,原理是什么?
- 两个独立的 DP 数组不应该开两个指针和内存池吗,为什么可以共用一个内存池?