[shkola] IOI 2003 interesna task

hehe, pozdravi hora. Da sazivim malko sastoianieto tuk. Ta sega gledah
podgotovacnite zadachi za IOI 2003. Mai kato za podgotovka sa gi
pozalili malko :P . Kakto i da e imashe edna po-interesna zadaca,  deto
mi se ste da ia poglednite i da ia obsadim. A eto ia i neia . 
TASK

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:

2-1-3
| | |
6 4 7
  |
  5
                          
                                                




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.

The input trees are given one per file.  Input cases are numbered 1
through 10 and are available via the contest website.

Input:

.       The first line of input contains a single integer K, specifying
the input case number.
.   The second line contains a single integer N.
.   Each of the next N-1 lines 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.

Example input:
0
7
2 6
1 2
1 4
4 5
3 7
3 1


Output:

.       The first line of output should contain the string .FILE balance
K., where K is the input case number.
.   The second line should contain a single integer, the number of the
node with minimum balance.
.    The third line should contain a single integer, the balance of that
node.

Example output:
FILE balance 0
1
2

CONSTRAINTS:

Running time    1 second of CPU
Memory  64 MB


SCORING

You will receive full points on each test case for which your program
produces a correct output file.  No partial credit will be given on any
test case.

Other related posts: