换根 DP 板子

以前一直以为这玩意是随机应变的。

结果还真能总结出板子。

当然也有一定的局限性，比如 \(dp\) 值必须 \(O(1)\) 算。但不影响正常使用。

ins：向 \(k\) 的子树信息中插入/删除 \(nx\) 的子树信息。

这里的 子树 在 dfs1 中是指以 \(1\) 为根的子树；dfs2 中是指以 \(k\) 为根。

recalc：重新计算 \(k\) 的 \(dp\) 值。

recalc 的信息储存在 dp_[k] 内，dp[k] 是最终的 \(dp\) 值。

void dfs1(int k, int fa)
{
	for(int i = h[k]; ~i; i = ne[i])
	{
		int nx = e[i];
		if(nx == fa)
			continue;
		dfs1(nx, k);
		ins(k, nx, 1);
	}
	recalc(k);
}

void dfs2(int k, int fa)
{
	dp[k] = dp_[k];
	for(int i = h[k]; ~i; i = ne[i])
	{
		int nx = e[i];
		if(nx == fa)
			continue;
		ins(k, nx, -1);
		recalc(k);
		ins(nx, k, 1);
		recalc(nx);
			
		dfs2(nx, k);
		
		ins(nx, k, -1);
		recalc(nx);
		ins(k, nx, 1);
		recalc(k);
	}
}