#include <string.h>
#define MAXN 1001
int adj[MAXN][MAXN]; // 为节点i邻接点数量
int visited[MAXN];
// 从start节点出发，but不经过x节点的节点数
int dfs(int start, int x)
{
visited[start] = 1;
int size = 1;
for (int i = 1; i <= adj[start][0]; i++)
{int next = adj[start][i];// 若邻接点不是x且未被访问，递归计算子树大小if (!visited[next] && next != x) {size += dfs(next, x);}
}
return size;
}int main() {
int n;
while (scanf("%d", &n) != EOF)
{for (int i = 1; i <= n; i++) {adj[i][0] = 0;}for (int i = 0; i < n - 1; i++){int u, v;scanf("%d %d", &u, &v);adj[u][++adj[u][0]] = v;adj[v][++adj[v][0]] = u;}int best_x = 1;// 最优平衡点int min_max_size = n;// 最大子树for (int x = 1; x <= n; x++) {memset(visited, 0, sizeof(visited));visited[x] = 1;// 标记已删除int max_size = 0;//算各子树的大小for (int i = 1; i <= adj[x][0]; i++) {int v = adj[x][i];if (!visited[v]){ // 邻接点v未被访问，→子树的根int sub_size = dfs(v, x);if (sub_size > max_size) {max_size = sub_size;}}}// 更新 最大子树更小或相等时x编号更小if (max_size < min_max_size || (max_size == min_max_size && x < best_x)) {min_max_size = max_size;best_x = x;}}printf("%d %d\n", best_x, min_max_size);}
◮：树的平衡点：删完掉该节点后，剩余子树中最大的子树节点数最小，邻接表存储树的结构，遍历每个节点删除x后，算剩余各子树的节点数DFS算删掉每个子树节点数，最后遍历◮：