以前一直以为这玩意是随机应变的。
结果还真能总结出板子。
当然也有一定的局限性，比如 \(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);
}
}