# CodeChef: May Long Challenge | Valid Paths | VPATH | Solution

Share:

View on Codechef

You are given a tree with NN nodes numbered from 11 to NN. A set SS of nodes is called valid if there exist two vertices uu and vv (possibly, u=vu=v) such that every node in SS lies on the simple path from uu to vv.

Count the number of valid sets modulo 109+7109+7. Two sets are different if one node is included in one set and not in the other. If there are multiple pairs (u,v)(u,v) making a set valid, that set is still only counted once.

### Input

• The first line contains an integer TT, the number of test cases. Then the test cases follow.
• Each test case contains NN lines of input.
• The first line contains a single integer NN, the number of tree nodes.
• Each of the next N−1N−1 lines contains two space-separated integers uu and vv representing an edge between nodes uu and vv.

### Output

For each test case, output in a single line the number of valid sets modulo 109+7109+7.

### Constraints

• 1≤T≤501≤T≤50
• 1≤N≤1051≤N≤105
• 1≤u,v≤N1≤u,v≤N
• Sum NN over all testcases is at most 5⋅1055⋅105.
• The given input is a valid tree.

• 1≤T≤101≤T≤10
• 1≤N≤3⋅1031≤N≤3⋅103

Subtask #2 (80 points): Original Constraints

### Sample Input

``````2
4
1 2
3 1
2 4
4
1 2
2 3
2 4
``````

### Sample Output

``````15
13
``````

### Explanation

Test Case 11: Every non-empty set is valid.

Test Case 22: The valid sets are {1}{1}, {2}{2}, {3}{3}, {4}{4}, {1,2}{1,2}, {1,3}{1,3}, {1,4}{1,4}, {2,3}{2,3}, {2,4}{2,4}, {3,4}{3,4}, {1,2,3}{1,2,3}, {1,2,4}{1,2,4}, {2,3,4}{2,3,4}.

``Solution will be updated here soon. Keep tracking``