关于此题长链剖分开空间的方式
查看原帖
关于此题长链剖分开空间的方式
75765
Starlight237楼主2020/8/27 16:33

在同是长链剖分 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;
  1. 这几种开空间的方式有什么区别吗,原理是什么?
  2. 两个独立的 DP 数组不应该开两个指针和内存池吗,为什么可以共用一个内存池?
2020/8/27 16:33
加载中...