Valid Paths CodeChef Solution in C++ | AskTheCode

CodeChef May Long Challenge Solution | Valid Paths (VPATH) solution | AskTheCode

---

Valid Paths (VPATH) CodeChef solution

Problem:

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

Count the number of valid sets modulo 10^9+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) making a set valid, that set is still only counted once.

---

Input:

• The first line contains an integer T, the number of test cases. Then the test cases follow.

• Each test case contains N lines of input.

• The first line contains a single integer N, the number of tree nodes.

• Each of the next N−1 lines contains two space-separated integers u and v representing an edge between nodes u and v.

---

Output:

For each test case, output in a single line the number of valid sets modulo 10^9+7.

---

Sample Input:

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

---

Sample Output:

15
13

---

Explanation:

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

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

---

Code:

The Solution has been uploaded in the AskTheCode Members Group. Please do visit there, and see the solution. Or click here to see the code.