ZOJ Problem Set - 2802
Preparing a problem for a programming contest takes a lot of time.
Not only do you have to write the problem description and write a
solution, but you also have to create difficult input files.
In this problem, you get the chance to help the problem setter
to create some input for a certain problem.
Given such a binary search tree, the following search procedure
can be used to locate a node in the tree:
The input file contains several test cases.
Each test case starts with an integer n (1 ≤ n ≤
the number of nodes in the optimal binary search tree.
For simplicity, the labels of the nodes will be integers from 1
to n. The following n lines describe the structure of
tree. The i-th line contains the labels of the roots
of the left and right subtree of the node with label i
(or -1 for an empty subtree). You can assume that the
input always defines a valid binary search tree.
For each test case, write one line containing the access frequency
for each node in increasing order of the labels of the nodes.
To avoid problems with floating point precision, the frequencies should
be written as integers, meaning the access probability for a node will be the
frequency divided by the sum of all frequencies. Make sure that you
write any integer bigger than 263 - 1 (the maximum value fitting in
C/C++ data type long long or the Java data type long).
Otherwise, you may produce any solution ensuring that there is exactly
one optimal binary search tree: the binary search tree given in the
3 -1 -1 1 3 -1 -1 10 -1 2 -1 3 -1 4 -1 5 -1 6 -1 7 -1 8 -1 9 -1 10 -1 -1 0
1 1 1 512 256 128 64 32 16 8 4 2 1
Note that the first test case in the sample input describes a tree looking like
2 / \ 1 3
Source: University of Ulm Local Contest 2005