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

Codechef

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.

Subtasks

Subtask #1 (20 points):

  • 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

See more posts here

1 thought on “CodeChef: May Long Challenge | Valid Paths | VPATH | Solution”

Leave a Comment

Your email address will not be published. Required fields are marked *

x