C++(g++ 7.5.0) 解法, 执行用时: 934ms, 内存消耗: 77356K, 提交时间: 2022-12-20 16:04:44

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans = INT_MAX, n;
int sz[1000006];
int dp[1000006];
vector<int>vec[1000006];
void dfs(int i, int fa) {
	sz[i] = 1;
	int mx1 = 0;
	int mx2 = 0;
	int mx3 = 0; //第三大的子树
	for (auto j : vec[i]) {
		if (j == fa)continue;
		dfs(j, i);
		sz[i] += sz[j];
		if (sz[j] > sz[mx1]) {
			mx3 = mx2;
			mx2 = mx1;
			mx1 = j;
		} else if (sz[j] > sz[mx2]) {
			mx3 = mx2;
			mx2 = j;
		} else if (sz[j] > sz[mx3]) {
			mx3 = j;
		}
		dp[i] = max(dp[mx1], sz[mx2]);
	}
	ans = min(ans, max(n - sz[i], max(dp[mx1], max(dp[mx2], sz[mx3]))));
}
int main() {
	int i, j, x, y;
	scanf("%d", &n);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}

C++ 解法, 执行用时: 696ms, 内存消耗: 64180K, 提交时间: 2021-10-24 15:40:13

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,sz[N],sig[N];
vector<int> g[N];
int res=2e9;
void dfs(int u,int fa){
	int mx=0,se=0,th=0;
	sz[u]=1;
	for(auto y:g[u]){
		if(y==fa) continue;
		dfs(y,u);
		sz[u]+=sz[y];
		if(sz[y]>=sz[mx]) {
			th=se;se=mx;mx=y;
		}else if(sz[y]>=sz[se]) {
			th=se;se=y;
		}else if(sz[y]>=sz[th]) th=y;
	}
	sig[u]=max(sig[mx],sz[se]);
	res=min(res,max({sz[th],sig[mx],sig[se],n-sz[u]}));
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	res=max(res,1);
	cout<<res<<'\n';
}