hackerrank偶数树解法讲解（偶数节点的森林）

Question

我在 hackerrank 上做这个名为 Even Tree 的问题：

https://www.hackerrank.com/challenges/even-tree

最初我不知道如何切割边缘并从树中建造森林。所以我在网上查了一下，在 stackeverflow 上看到了这个答案：

Obtain forest out of tree with even number of nodes

好吧，只是计算 children 的数量看起来简单多了，我用 C++ 实现了它：

#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main() {
  int N, M, ans = 0;
  cin >> N >> M;
  vector<int> tree(N+1);
  vector<int> count(N+1);

  fill(count.begin(), count.end(), 1);
  for(int i = 0; i < M; i++) {
    int p, q;
    cin >> p >> q;
    tree[p] = q;

    int root = tree[p];

    // updating ancesors child count
    while(root) {
      count[root] += count[p];
      root = tree[root];
    }
  }

  int counter = 0;
  // displaying results
  for(int i = 2; i < count.size(); i++) {
    cout << count[i] << " ";
    if(count[i]%2 == 0)
      counter++;
  }
  cout <<"\nans : " <<  counter << endl;
  return 0;
}

我的问题是：这种方法是如何工作的？ children 的数量如何与选择边数最少的树相关联？我不只是想复制解决方案，我想了解其背后的实际逻辑。请帮忙

Answer 1

首先，问题是说所有测试用例（所有输入树），存在一种删除边缘的方法，以便保留森林的均匀大小。当然，由于结果森林中的每棵树的大小都是偶数，这意味着节点总数 N 必须是偶数。即使树 也必须 有解决方案，因为至少它们可以删除 0 条边以形成均匀的森林。

注意有一些边不能被删除，即连接叶节点的边。于是我脑子里冒出一些贪心的念头，结果证明我可以证明它们，于是就变成了可以解决问题的贪心算法。

我声称

a) 任何偶数大小的子树，我们可以安全地从原始图中删除它们以减少问题而不影响结果，通过删除子树根的边和它的parent（如果存在）

b) 任何奇数大小的子树，我们可以用单个节点替换整个子树以减少问题。子树根的边缘及其 parent CANNOT 被删除（如果存在）

我们用反证法证明a)。假设如果我们删除图的偶数子树将使问题从可解变为不可解。考虑去掉偶数子树后的图，如果是奇数，则原图也无解；如果它的大小是偶数，那么它必须在删除偶数子树后有解决方案。两种情况都产生矛盾。

b) 很简单，因为子树的大小是奇数，它的奇偶性与单个叶节点相同，必须连接它的 parent.所以我们可以用单个节点代替子树来减少问题。

通过a)和b)，我们可以从树的叶子做一个贪心算法（因为我们已经知道必须选择连接叶子的边，它们正在形成子树，我们可以从这里开始减少问题）

将所有叶子与其 parents
对于所有形成的子树，如果子树是偶数，则全局答案计数器加1，移除子树；如果子树是奇数，则将其替换为单个节点（现在也是叶子节点）。
重复2直到最多剩下1个节点

就是这样。从概念上讲，这就是算法。

虽然您可以使用许多不同的方法来实现它，但我使用 DFS，它非常直接地将此算法转换为代码。

有的只是统计children的个数，因为这可以判断子树是奇数还是偶数。

甚至有人只计算偶数度的节点数！（这是迄今为止我所知道的最聪明的解决方案）

但它们背后都有一个共同的概念：判断子树是否为奇数大小或偶数大小，将它们移除（并增加答案计数器）或用单个节点替换它们以减少问题。

所有实现也具有相同的复杂度 O(N)。

这是我接受的代码：

#include<bits/stdc++.h>
using namespace std;

int w[105][105] = {0}, v[105] = {0};
int n,m,ans=0;

int dfs(int x){
    v[x] = 1;
    int son = 0;
    for(int i=0; i<105;i++) 
        if(w[x][i] && !v[i]) son += dfs(i);
    if(son % 2) { ans++; return 0;}
    return 1;
}

int main() {
    scanf("%d%d", &n,&m);
    for(int i=0,a,b; i<m;i++){
        scanf("%d%d", &a,&b);
        w[a][b] = w[b][a] = 1;
    }
    dfs(1);
    printf("%d\n", ans-1);  
    return 0;
}

hackerrank偶数树解法讲解（偶数节点的森林）

hackrerank Even tree solution explanation(forest with even number nodes)

algorithm

tree

graph