将一个双色树转换为二分树

Question

给定一个双色树(比如红色和蓝色(，我想通过交换相邻节点的颜色将其转换为二分树。此外，我希望将掉期数量保持在最低限度。我无法处理最小交换部分。尽管我已经编写了一个dfs代码，它假设根为红色，并计算所需的红色和蓝色节点的数量。如果我们有足够的颜色使树成为二分树，我们如何计算最小交换？

void dfs(vector<vector<ll>> &adj , ll node , ll parent , ll val)
{
if(val == 0) red++;
else 
{
blue++;
}
for(auto x : adj[node])
{
if(x!=parent)
dfs(adj ,  x , node , val^1 );
}
return;
}
if(givenred == red || givenred == blue)
// count minimal swaps
else
// not possible

Answer 1

一旦您决定了哪些节点需要使用哪种颜色，那么：

1. 如果您还没有根，请选择一个根
2. 对于每个子树，计算该子树中应该有多少红色节点
3. 对于每个子树，计算该子树中有多少红色节点
4. 把每个子树的差值加起来

对于每个子树，差异的大小是必须在其父树的边上发生的交换次数。

该算法需要线性时间，因为每个步骤都可以用DFS在线性时间内完成。您可以尝试两种颜色分配(根红色或根蓝色(，并选择较小的总数。