题解：P1670 [USACO04DEC] Tree Cutting S
SegmentSplay
·
·
题解
O(n^2) 思路
注意到 n \leq 10^4，所以可以枚举每个点把树掰开判断剩下的连通块里有没有大于 \frac n2 的。
时间复杂度 O(n^2) 可以通过。
好的绿题被我们变成了黄题。
## $O(n)$ 思路
前置芝士：[树的重心](https://oi-wiki.org/graph/tree-centroid/) 。
你说的对，虽然 $O(n^2)$ 的时间复杂度能过，但还是太吃时间了，有没有更强势的算法？
有的兄弟，有的！
考虑一种算法，可以在一次搜索中求出所有点的最大子树大小。
你想到了什么？没错，就是树的重心！
大体思路：
任意以一个点作为树的根，进行一次 DFS，每次用搜到的点的最大子树大小更新当前点的最大子树大小。
- 由于这是一棵无根树，所以父节点的子树也算一棵合法的子树。计算方法：用总节点数减去当前节点其他所有子树的节点数。
- 还有一个细节：众所周知，树的重心一定满足其最大子树节点数小于总结点数一半的性质，而一棵无根树肯定存在一个重心。所以，**无解的情况其实根本不存在**！
## AC 代码
说明: $s_i$ 表示对于当前节点，以 $1$ 为根时，所有子树的节点数总和。$d_i$ 表示 节点 $i$ 最大子树的节点个数。
存图采用利用 `vector` 实现的邻接表方式。
吸上氧气以后跑的飞快。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool vis[10005];
int s[10005],n,d[10005];
vector<int>v[10005];
void dfs(int x)
{
vis[x]=s[x]=1;
int ans=0;
for(int i=0;i<=v[x].size()-1;i++)
{
int t=v[x][i];
if(vis[t])
{
continue;
}
dfs(t);
s[x]+=s[t];
ans=max(ans,s[t]);
}
ans=max(ans,n-s[x]);
d[x]=ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++)
{
int u,vv;
cin>>u>>vv;
v[u].push_back(vv);
v[vv].push_back(u);
}
dfs(1);
for(int i=1;i<=n;i++)
{
if(d[i]<=(n/2))
{
cout<<i<<'\n';
}
}
return 0;
}
```