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 n1 line, consisting of two integers a and b  number of nodes connected by an edge. Nodes are numbered from 0 to n1. 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
hide comments
horro:
20200801 19:55:27
simple dp on tree problem 

mrdevesh_00:
20200716 11:14:42
can anyone explain me the problem statement.


nadstratosfer:
20190510 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 32bit 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. 

sonorous:
20171028 13:02:12
AC in one go!!! DFS with slight modifications! 

heisenberg0820:
20170629 17:04:19
Very poor problem statement though


imsaral:
20170626 11:02:39
My 100th on Spoj :) 

anurag44:
20170612 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 !! 

lalywr:
20170609 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 _ 

pranjal priyadarshi:
20170423 06:55:21
Can someone please explain the input out of the problem how do we build the tree from the given input output 

vengatesh15:
20170129 11:03:20
AC in 1 go:) 
Added by:  Spooky 
Date:  20100309 
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/ 