| Submit | All submissions | Best solutions | Back to list |
PYRA - Treeramids |
Daniel is building towers. He has a big amount of block of the size 1x1xK (for any K). Out of them he is building towers according to the following rules: the longest block is put in the basement of the tower. Several towers built by the same rules can be put on this block. The distance between the bases of those towers should be 1 and the distance between the bases of the towers and the edges of the common basement should be 1. There should be a block of the length 1 on the top of each tower. Daniel encodes every tower with root tree. For example:
The root of the tree corresponds to the basement of the tower. Its descendants correspond to the towers standing on it. The leaves correspond to the blocks of the size 1x1x1 on the tops. Given the root tree describing one of those structures, calculate the total volume of the structure.
Input
The first line of input contains the number t - the number of tests. Next comes the description of t tests. Each test starts with an integer n - the number of nodes of the tree. This is followed by n-1 line, consisting of two integers a and b - number of nodes connected by an edge. Nodes are numbered from 0 to n-1. The root of the tree will always be a node with number 0. Otherwise the nodes and edges can go in any order.
Constraints
1 <= t <= 25
1 <= n <= 10^4
Output
For each test case print the total volume of the structure build according to the rules in the problem statement.
Example
Input: 2 7 0 1 2 0 0 3 2 4 5 2 6 3 3 1 2 1 0 Output: 25 9
| Added by: | Spooky |
| Date: | 2010-03-09 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
| Resource: | Advancement Spring 2010, http://sevolymp.uuuq.com/ |
hide comments
|
||||||
|
2020-08-01 19:55:27
simple dp on tree problem |
||||||
|
2020-07-16 11:14:42
can anyone explain me the problem statement. Its the worst problem statement i have ever seen. |
||||||
|
2019-05-10 16:02:23
This problem's comment section features the weirdest compilation of unfounded criticisms I've seen on this site. The statement left me with no questions and if I had any, the diagram makes everything pretty intuitive; the constraints are correct, the answer fits in 32-bit integer (it has to if you can imagine the worst case with the given constraints) and finally, despite psetter having a poor reputation in this respect, time limit gives a correct solution no grief, even in Python. Good problem. |
||||||
|
2017-10-28 13:02:12
AC in one go!!! DFS with slight modifications! |
||||||
|
2017-06-29 17:04:19
Very poor problem statement though Recursion :) AC in one go :D |
||||||
|
2017-06-26 11:02:39
My 100th on Spoj :) |
||||||
|
2017-06-12 11:04:19
Nyc problem though problem description is difficult to understand. I suggest you to see the diagram carefully and read this line "the distance between the bases of those towers should be 1 and the distance between the bases of the towers and the edges of the common basement should be 1. " . You will get it. Applied DFS..AC in one go !! |
||||||
|
2017-06-09 17:04:24
This is probably the worst ever worded question on SPOJ . I really don't understand how the administrators even approve this question . There is no sample / proper explanation of the test cases , the author must provide some clarifications about the test cases . Silly people -_- |
||||||
|
2017-04-23 06:55:21 pranjal priyadarshi
Can someone please explain the input out of the problem how do we build the tree from the given input output |
||||||
|
2017-01-29 11:03:20
AC in 1 go:-) |
||||||
RSS