solution - CF1375G

littlebug · 2025-09-17 15:49:56 · 题解

在线征集能不看题解想到二分图做法的神人，反正我是怎么也不可能想到的 /ll

Sol 1 - 换根 dp

这个还是比较常规的。

令 f_u 为把子树 u 内的点全都挂到点 u 上的最小操作次数。那么需要对 u 的每个孙子都进行一次操作来将其挂到 u 上，而且显然没有更好的方案了，所以枚举 u 的所有孙子 x，有：

f_u = \sum (f_x + 1)

然后换根，令 g_u 为以 u 为根，把所有点都挂在 u 上的最小操作次数。

对于 v \in u.son，考虑转移：

首先，在原树中的子树 v 的贡献不变，为 f_v。
考虑 u 的其他儿子对 v 的贡献，显然这些点都需要进行一次操作以挂到 v 上，贡献为 \displaystyle \sum _{x \in u.son \land x \ne v} (f_x + 1)。
还没完。我们发现目前为止根本没有换根，这是因为我们的操作是对于中间隔一个点的两个点的，而不是相邻两个点。\ 所以还要考虑 u 的父亲 fa 的贡献，这个显然是以 fa 为根时的答案减去其中包含的子树 u 的部分，贡献即为 \displaystyle g_{fa} + 1 - \sum _{x \in u.son} (f_x + 1)（加一是因为还要用一次操作把 fa 挂到 v 上）。

于是得到转移式子：

g_v = f_v + \sum _{x \in u.son \land x \ne v} (f_x + 1) + g_{fa} + 1 - \sum _{x \in u.son} (f_x + 1)

注意到有可以约掉的项，但是并不能约掉，因为会出现一些 v 没有对应的 fa 的情况，这时候最后那一块就不用加了。

代码：

int n,f[N],g[N],s[N];
vector <int> p[N];

il void dfs1(int u,int ufa)
{
    for(auto v:p[u]) if(v^ufa)
    {
        dfs1(v,u),s[u]+=f[v]+1;
        for(auto x:p[v]) x^u && (f[u]+=f[x]+1);
    }
}

il void dfs2(int v,int u,int fa)
{
    v^1 && (g[v]=f[v]+s[u]-(f[v]+1));
    fa && (g[v]+=g[fa]+1-s[u]);
    for(auto x:p[v]) x^u && (dfs2(x,v,u),1);
}

il void solve()
{
    read(n),_::r(p,n-1,false);
    dfs1(1,0),g[1]=f[1],dfs2(1,0,0);
    write(mnele(g+1,g+n+1));
}

Sol 1.5 - 错误（？）的换根 dp

为什么我在算最后一块的时候，只减掉了 v 的贡献，但是并没有减掉 u 的其他儿子的贡献，这样还过了？

这个错误的换根 dp 式子是这样的：

g_v = f_v + \sum _{x \in u.son \land x \ne v} (f_x + 1) + g_{fa} + 1 - (f_v + 1)

有无大佬可以解释下为什么 qwq，或者给个 hack 数据？

submission

Sol 2 - 黑白染色

注意到树是一个二分图。但是注意不到，真的注意不到。

手玩一下可以发现，在对树进行黑白染色后，每次操作恰好能改变一个点的颜色（对应操作中的点 a）。

而菊花图就是一个只有一个点是黑色（或白色）的二分图，所以考虑是否在构成菊花图之前每次操作都可以选择改变一个黑点还是改变一个白点。

发现这是可以的，因为如果图上有 \ge 2 个白点，那么一定存在两个白点中间由一个黑点连接，于是操作这两个白点就可以了。

所以答案就是原树中黑点数和白点数的较小值减一。

太神仙了。

代码：

int n,cnt=0;
vector <int> p[N];

il void dfs(int u,int ufa,bool op)
{
    op && ++cnt;
    for(auto v:p[u]) v^ufa && (dfs(v,u,!op),1);
}

il void solve(int __Ti)
{
    read(n),_::r(p,n-1,false);
    dfs(1,0,1);
    write(min(cnt,n-cnt)-1);
}

华风夏韵，洛水天依！