题解 P6591 【[YsOI2020]植树】

WanderingTrader · 2020-06-17 22:17:34 · 题解

这题是一道树上操作题，难度不大。

题目分析

其实就是判断一个多叉树中的各子树大小是否相同。
如果以每个节点为根重构树，复杂度将达到O(n^2)，在1\le n\le10^6的情况下显然是不行的，只能拿到Subtask 1的40分。这样的数据规模要求我们把复杂度降到O(n\log n)甚至常数稍大的O(n)。
这意味着我们只能执行一次重构树操作，就以节点1为根吧。

我们自造一组强度略高的数据，如下：

7
1 2
3 1
4 2
5 2
4 6
3 7

手算得样例输出：

5 6 7

我们把整棵树画出来即为：

以1为根，计算各结点的子树大小（包含自己）：

7 4 2 2 1 1 1

然后让每个节点找自己子结点的子树大小，以及n减去自己大小的值：

4 2
2 1 3
1 5
1 5
6
6
6

我们看到，只有第5,6,7行的数字完全相同，满足条件，所以输出5 6 7
大体思路就是这样，主要还是看代码吧。

代码

首先我们用一个邻接表：

#define N 1000005
#define _for(x,y) for(int i = x;i <= y;i ++)
vector <int> es[N];

初始化：

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define _for(x,y) for(int i = x;i <= y;i ++)
vector <int> es[N];
bool root[N];
int d[N],n;
int main()
{
    scanf("%d",&n);
    int u,v;
    _for(1,n - 1)
    {
        scanf("%d%d",&u,&v);
        es[u].push_back(v);
        es[v].push_back(u);
    }
    return 0;
}

这里我们对for循环做了一个重定义，主要是想少打几个字吧。