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


hide comments
sonorous: 2017-10-28 13:02:12

AC in one go!!! DFS with slight modifications!

heisenberg0820: 2017-06-29 17:04:19

Very poor problem statement though
Recursion :)
AC in one go :D

imsaral: 2017-06-26 11:02:39

My 100th on Spoj :)

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

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

pranjal priyadarshi: 2017-04-23 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: 2017-01-29 11:03:20

AC in 1 go:-)

siddharth_0196: 2017-01-01 14:14:19

Recursion will do the trick!

Sarthak Munshi: 2016-07-05 19:55:37

DFS with a little twist !

krish: 2015-03-28 14:51:39

Simple recursive DFS that's it:)


Added by:Spooky
Date:2010-03-09
Time limit:0.417s
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/