自动搬运

查看原文

来自洛谷，原作者为

	SegmentSplay 线段树好闪，拜谢线段树！

搬运于2025-08-24 21:27:45，当前版本为作者最后更新于2025-08-12 11:16:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$O(n^2)$ 思路

注意到 $n \leq 10^4$，所以可以枚举每个点把树掰开判断剩下的连通块里有没有大于 $\frac n2$ 的。

时间复杂度 $O(n^2)$ 可以通过。

好的绿题被我们变成了黄题。

$O(n^2)$ 时间复杂度的代码请自己实现。绝对不是我懒得写第二个代码了

$O(n)$ 思路

前置芝士：树的重心 。

你说的对，虽然 $O(n^2)$ 的时间复杂度能过，但还是太吃时间了，有没有更强势的算法？

有的兄弟，有的！

考虑一种算法，可以在一次搜索中求出所有点的最大子树大小。

你想到了什么？没错，就是树的重心！

大体思路： 任意以一个点作为树的根，进行一次 DFS，每次用搜到的点的最大子树大小更新当前点的最大子树大小。

• 由于这是一棵无根树，所以父节点的子树也算一棵合法的子树。计算方法：用总节点数减去当前节点其他所有子树的节点数。

• 还有一个细节：众所周知，树的重心一定满足其最大子树节点数小于总结点数一半的性质，而一棵无根树肯定存在一个重心。所以，无解的情况其实根本不存在！

AC 代码

说明: $s_i$ 表示对于当前节点，以 $1$ 为根时，所有子树的节点数总和。$d_i$ 表示 节点 $i$ 最大子树的节点个数。

存图采用利用 vector 实现的邻接表方式。

吸上氧气以后跑的飞快。

#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;
}