409652: GYM103660 E Disjoint Path On Tree

You are given a tree consisting of $$$n$$$ vertices. Recall that a tree is an undirected connected acyclic graph.

Now, calculate the number of simple path pairs that each pair of simple paths does not pass through the same vertex. Note that $$$pair(Path_i,Path_j)$$$ and $$$pair(Path_j,Path_i)$$$ should only be calculated once. As the answer may be too big, output the answer module $$$10^9+7$$$.

The simple path is the path that visits each vertex at most once. The path only visits a single vertex is also a path.

The first line contains a single integer $$$T (1 \le T \le 2 \times 10^5)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n (1 \le n \le 2 \times 10^5)$$$ — the number of vertices.

The next $$$n-1$$$ lines of each test case describe the edges of the tree in form of $$$u_i, v_i(1\le u_i,v_i \le n, u_i \ne v_i)$$$. It is guaranteed that given graph is a tree.

It is guaranteed that $$$\sum{n} \le 2 \times 10^5$$$ over all test cases.

For each test case, output a single integer in a line — the answer module $$$10^9+7$$$.

1
3
1 2
1 3

5

$$$5$$$ pairs of paths in the sample are:

• $$$(1,2)$$$
• $$$(1,3)$$$
• $$$(2,3)$$$
• $$$(1-2,3)$$$
• $$$(1-3,2)$$$