首页 > 代码库 > POJ 1655 Balancing Act【树的重心】

POJ 1655 Balancing Act【树的重心】

2024-11-15 22:48:02   202人阅读

Balancing Act

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 14251 Accepted: 6027

Description

Consider a tree T with N (1 <= N <= 20,000) nodes numbered 1...N. Deleting any node from the tree yields a forest: a collection of one or more trees. Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T.
For example, consider the tree:
技术分享

Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two.

For each input tree, calculate the node that has the minimum balance. If multiple nodes have equal balance, output the one with the lowest number.

Input

The first line of input contains a single integer t (1 <= t <= 20), the number of test cases. The first line of each test case contains an integer N (1 <= N <= 20,000), the number of congruence. The next N-1 lines each contains two space-separated node numbers that are the endpoints of an edge in the tree. No edge will be listed twice, and all edges will be listed.

Output

For each test case, print a line containing two integers, the number of the node with minimum balance and the balance of that node.

Sample Input

172 61 21 44 53 73 1

Sample Output

1 2

Source

POJ Monthly--2004.05.15 IOI 2003 sample task
题目链接：http://poj.org/problem?id=1655

题目很好理解，就是去掉树上的一个节点，看看剩下的子树中最大的是多少，然后在这些最大值中求一个最小值，如果有多个点都是最小值，那么找一个序号最小的节点。输出节点号，和最小值。

经过简单分析，DFS深度优先搜索可以解决，只需要求出每个节点下子树的总结点个数即可。

这题其实是求重心的裸题！

举例说明：

设有一棵树20个节点，其中有一个节点为u，u有两个孩子节点，设u以下有10个节点，两个孩子分别有6和4个节点，那么对于u来说，最大是多少，应该是20 - 10,6,4中的最大的也就是10.这样等把所有节点的最大值求出后，再求1-n中的最小值，输出该点以及最小值即可。

算法就是DFS，计算出每个节点下的总数，然后保留本节点下的孩子节点子树中的最大值，然后和自己的祖先节点比较求出最大值，最后枚举最小值。

这题一定要建一个双向图，因为树是无向的。

下面是AC代码：

 1 #include <stdio.h> 2 #include <string.h> 3 #define max(a,b) (a)>(b)?(a):(b) 4 const int maxn=20010; 5 struct Edge//前向星存边 6 { 7     int to,next; 8 }edge[maxn<<1];//保存双向图 9 int head[maxn],tot;10 inline void init()//初始化操作11 {12     memset(head,-1,sizeof(head));13     tot=0;14 }15 inline void addedge(int u,int v)//加边16 {17     edge[tot].to=v;18     edge[tot].next=head[u];19     head[u]=tot++;20 }21 int dp[maxn];//每个节点去掉后其他子树的点数22 int num[maxn];//每个节点下的节点总数23 int n;24 inline void DFS(int u,int pre)25 {26     dp[u]=0;//初始化27     num[u]=1;//初始化28     for(int i=head[u];i!=-1;i=edge[i].next)29     {30         int v=edge[i].to;31         if(v==pre)32             continue;33         DFS(v,u);34         dp[u]=max(dp[u],num[v]);//求根节点下儿子节点中的最大值35         num[u]+=num[v];//求根节点下的所有节点数36     }37     dp[u]=max(dp[u],n-num[u]);//祖先节点总数的最大值和根节点下儿子节点中的最大值作为本节点的最大值38 }39 int main()40 {41     int T;42     scanf("%d",&T);43     int u,v;44     while(T--)45     {46         scanf("%d",&n);47         init();48         for(int i=1;i<n;i++)//建图49         {50             scanf("%d%d",&u,&v);51             addedge(u,v);52             addedge(v,u);53         }54         DFS(1,-1);55         int ans1=1,ans2=dp[1];56         for(int i=2;i<=n;i++)//求最小值57         {58             if(ans2>dp[i])59             {60                 ans1=i;61                 ans2=dp[i];62             }63         }64         printf("%d %d\n",ans1,ans2);65     }66     return 0;67 }

 

POJ 1655 Balancing Act【树的重心】


联系
我们