在一棵树中，去掉一个点，使得剩下的每一颗树的结点数最多的那颗树，结点数最少。
具体解法看注释.
- /*
- 定义dp[i]为去掉i结点，剩下的树里，结点最多的那颗树的结点数。
- 可分为2类情况。
- 1、由于i结点的儿子结点都成了一棵树的根节点，所以dp[i] = (i的每个儿子所拥有的结点数，的最大值)。
- 2、而另一种情况就是剩下的那棵树，所以dp[i] = N-num[i]。
- 其中num[i]表示以i为根的树的所有结点数，可以dfs求出。
- */
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- using namespace std;
- #define MAXN 20005
- int N;
- vector<int> node[20005];
- int num[MAXN];
- int dp[MAXN];
- bool vis[MAXN]; //由于为无向图，所以用这个来标记此结点是否计算过。
-
- int dfs(int id)
- {
- int n=node[id].size();
- vis[id]=1;
- num[id]=1;
- for(int i=0;i<n;i++)
- {
- if(!vis[node[id][i]])
- num[id]+=dfs(node[id][i]);
- }
- return num[id];
- }
- void cal(int id)
- {
- int n=node[id].size();
- int k;
- vis[id]=1;
- for(int i=0;i<n;i++)
- {
- k=node[id][i];
- if(vis[k]) //只有可能是它老爸
- {
- dp[id]=max(dp[id],N-num[id]);
- }
- else //它儿子
- {
- dp[id]=max(dp[id],num[k]);
- cal(k);
- }
- }
- }
- int main()
- {
- int t,a,b;
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d",&N);
- for(int i=1;i<=N;i++)
- node[i].clear();
- memset(dp,0,sizeof(dp));
- for(int i=1;i<N;i++)
- {
- scanf("%d%d",&a,&b);
- node[a].push_back(b);
- node[b].push_back(a);
- }
- memset(vis,0,sizeof(vis));
- dfs(1);
- memset(vis,0,sizeof(vis));
- cal(1);
- int ans=0x7fffffff;
- int k;
- for(int i=1;i<=N;i++)
- {
- if(dp[i]<ans)
- {
- ans=dp[i];
- k=i;
- }
- }
- printf("%d %d\n",k,ans);
- }
- return 0;
- }