以前一直以为这玩意是随机应变的。
结果还真能总结出板子。
当然也有一定的局限性,比如 \(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);
}
}
标签:recalc,int,板子,nx,fa,DP,ins,换根,dp
From: https://www.cnblogs.com/ningago/p/17360081.html