[YsOI2020]植树

植树

题目描述

Ysuperman 有一棵 nn 个节点的无根树 TT。如果你不知道树是什么，TA 很乐意告诉你，树是一个没有环的无向联通图。

既然树是无根的，那就没有办法种植。Ysuperman 研究了很久的园艺，发现一个节点如果可以成为根，它必须十分平衡，这意味着以它为根时，与它直接相连的节点，他们的子树大小都相同。

你作为幼儿园信息组一把手，Ysuperman 给你一棵树，你能在 1s1s 内找到所有可能成为根的节点吗？

分析

大致思路为求出每个节点作为根节点时，是否满足条件。每个子树的节点个数时时必须要知道的。我们可以任意选取一个点为根节点，来计算每个子树大小(d[x])。以下以选取1号点为例。

void dfs(int u, int fa)
{
    d[u] = 1;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        d[u] += d[j];
    }
    if(u != 1 && num && num != n - d[u]) root[u] = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在求以u为根节点的子树大小的过程中，我们可以顺便并比较不同子树大小是否相同，可以设定num，用来记录其中一个子树的大小。不想打则x不能成为根节点

 if(!num) num = d[j];
 else
 {
 	if(d[j] != num) root[u] = 0;
 }
1
2
3
4
5

在上述比较中，我们只能比较**x结点以下的子树是否相同，所以还需要再比较一下其上方的部分**，根节点1或者不存在子树的,也需要再进一步筛出。

if(u != 1 && num && num != n - d[u]) root[u] = 0;
1

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10, M = 2 * N;

int n, m, k, t;
int h[N], e[M], ne[M], idx;
int d[N], root[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
    int num = 0;
    d[u] = 1;

    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        d[u] += d[j];
        if(!num) num = d[j];
        else
        {
            if(d[j] != num) root[u] = 0;
        }
    }
    if(u != 1 && num && num != n - d[u]) root[u] = 0;
}

int main()
{
    memset(root, 1, sizeof root);
    memset(h, -1, sizeof h);
    cin >> n;

    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    dfs(1,0 );

    int cnt = 0;
    for(int i = 1; i <= n; i ++)
        if(root[i]) cout << i << " ";

    puts("");
    for(int i = 1; i <= n; i ++) cout <<d[i] << "--";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59