【题目链接】
【算法】
这题描述有些繁琐，先简化一下题意 ： 对于一棵无根树，删除一个节点，使得其余的联通块中，最大的联通块最小
那么，这题就很好做了
对这棵树进行一遍DFS，求出每个节点为根的子树的大小（记为size），再求出删除节点后，子树中最大的联通块的大小（记为mx)
那么，删除一个点后（设这个点为x），最大的联通块就是max{n - size[x],mx[x]}，求最小的即可
【代码】
此题用std :: vector存储邻接表会离奇Runtime Error，令笔者不解
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 100010 const int INF = 2e9; int i,n,u,v,ans = INF,tmp,tot; vector< int > res; int Head[MAXN],Next[MAXN],U[MAXN],V[MAXN],fa[MAXN],size[MAXN],mx[MAXN]; inline void addedge(int u,int v) { tot++; U[tot] = u; V[tot] = v; Next[tot] = Head[u]; Head[u] = tot; } inline void dfs(int x) { int i,y; size[x] = 1; for (i = Head[x]; i; i = Next[i]) { y = V[i]; if (fa[x] != y) { fa[y] = x; dfs(y); size[x] += size[y]; mx[x] = max(mx[x],size[y]); } } } int main() { scanf("%d",&n); for (i = 1; i < n; i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1); for (i = 1; i <= n; i++) { tmp = max(mx[i],n-size[i]); if (tmp < ans) { ans = tmp; res.clear(); res.push_back(i); } else if (tmp == ans) res.push_back(i); } for (i = 0; i < res.size() - 1; i++) printf("%d ",res[i]); printf("%d ",res[res.size()-1]); return 0; }