Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Interesting Triplets (Hard)

By DiscoFighter47 · Limits 2s, 512 MB

Niko just learned about tree. Not those give us oxygen but tree from graph theory. After a while, he figured out that if he takes three distinct nodes A, B, C from a tree, sometimes it may occur that sum of the shortest distance from A to B and from B to C is equal to the shortest distance from A to C. This breathtaking discovery excites Niko a lot. He named such triplet as an interesting triplet. Out of curiosity, Niko tried to count down the number of such interesting triplets in a given tree. But alas, he is a newbie in graph theory and messed around the calculation. Niko heard that you are one of the best programmers from NSU and you are going to participate in “Intra NSU Programming Contest 2018”. So he came to you and ask for your help. Help Niko to solve his problem.

Input

Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with a integers n (1 ≤ n ≤ 100000) donating the number of nodes. The next n-1 lines contain two integers u, v (1 ≤ u, v <= n, uv) indicating that there is an edge between u and v. There’ll be exactly one path between any pair of nodes u and v.

Note: Sum of the number of nodes over all test cases ≤ 500000.

Output

For each case, print a line containing the case number and the number of interesting triplets.

Sample

InputOutput
2
3
1 2
2 3
2
1 2
Case 1: 2
Case 2: 0

For case 1, interesting triplets are (1,2,3) and (3,2,1)

For case 2, there is no interesting triplet.

Discussion

Statistics


79% Solution Ratio

NirjhorEarliest, Jul '18

dip_BRURFastest, 0.1s

VasiljkoLightest, 6.6 MB

ovis96Shortest, 838B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.