题目链接：?id=1655题目大意：定义平衡数为去掉一个点其最大子树的结点个数，求给定树的最小平衡数和对应要删的点题目分析：其实就是求树的重心，找到一个点，，其所有的子树中最大的子树的节点数最少，那么这个点就是这棵树的重心，删除重心后，剩余的子树更加平衡正好满足题意，下面说明如何求重心，因为这是一棵无根树，因此要连双向边，任取一个顶点作为根，记dp[i]为以结点i为子树根的子树的结点个数（注意这里不包括子树根本身），所以dp[i] += dp[son] + 1，加1是因为要算上其儿子自己这个结点，然后对于每个子树求出来的dp[son] + 1我要取最大，设最大为b，注意这里还要再取一次最大b = max(b, n – dp[i] – 1)，因为这是一棵无根树，当前结点i也可以做这棵树的根，所以这里把剩余部分也当作它的儿子（即在当前dfs序下的其祖先和兄弟部分）画个图可以看的更明白些#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 20005;int const INF = 0x3fffffff;struct EDGE{int to, next;}e[MAX * 2];int head[MAX], dp[MAX];bool vis[MAX];int n, cnt, num, ans, b;void Add(int u, int v){e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt ++;}void Init(){cnt = 0;n = 0;num = INF;ans = n;memset(head, -1, sizeof(head));memset(dp, 0, sizeof(dp));memset(vis, false, sizeof(vis));}void DFS(int rt){vis[rt] = true;dp[rt] = 0;int b = 0;for(int i = head[rt]; i != -1; i = e[i].next){int son = e[i].to;if(!vis[son]){DFS(son);dp[rt] += dp[son] + 1;b = max(b, dp[son] + 1);}}b = max(b, n – dp[rt] – 1);if(b < num || (b == num && rt < ans)){num = b;ans = rt;}return; }int main(){int T;scanf("%d", &T);while(T–){Init();int st;scanf("%d", &n);for(int i = 0; i < n – 1; i++){int u, v;scanf("%d %d", &u, &v);Add(v, u);Add(u, v);st = u;}DFS(st);printf("%d %d\n", ans, num);}}
读书须用意，一字值千金。
