Apple OA | 80LPA CTC | 2027 Grad | SWE-1 | Camera On
This was on-campus test - hence could not take image of the problem.
Apple OA - Count Paths Through Each Node
You are given an undirected tree with N nodes numbered from 1 to N.
A path is a sequence of one or more edges connecting two distinct nodes in the tree.
Since the tree is undirected, the paths (u, v) and (v, u) are considered the same path.
Also, a path containing only a single node is not considered valid. Therefore, every valid path must contain at least 2 nodes.
For every node i, determine the number of distinct valid paths that contain node i.
Because the number of paths can be very large, every answer must be returned modulo 10^9 + 7.
Example
Consider the following tree:
1 — 2 — 3
The distinct valid paths are:
(1,2)
(2,3)
(1,2,3)
Now count the paths containing each node:
Node 1 is present in (1,2) and (1,2,3) → 2
Node 2 is present in (1,2), (2,3), and (1,2,3) → 3
Node 3 is present in (2,3) and (1,2,3) → 2
Therefore, the output is:
2 3 2
Input Format
The first line contains an integer T, the number of test cases.
For each test case:
The first line contains an integer N, the number of nodes.
The next N - 1 lines each contain two integers u and v, representing an undirected edge between nodes u and v.
The given graph is guaranteed to be a tree.
Output Format
For each test case, print N integers.
The i-th integer represents the number of distinct valid paths containing node i, modulo 10^9 + 7.
Formally:
answer[i] = (number of valid paths containing node i) % (10^9 + 7)
Paths containing only a single node are not included.
Sample Input
2
3
1 2
2 3
2
1 2
Sample Output
2 3 2
1 1
Explanation of Sample
Test Case 1
The tree is:
1 — 2 — 3
The valid paths are:
(1,2)
(2,3)
(1,2,3)
Therefore:
Node 1 → 2 paths
Node 2 → 3 paths
Node 3 → 2 paths
Output:
2 3 2
Test Case 2
The tree is:
1 — 2
There is only one valid path:
(1,2)
Therefore:
Node 1 → 1 path
Node 2 → 1 path
Output:
1 1
Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 2 × 10^5
1 ≤ u, v ≤ N
u ≠ v
The graph is guaranteed to be a tree.
The sum of N across all test cases does not exceed 2 × 10^5.
The function should return an array of N integers, where the i-th element contains the number of valid paths passing through node i, modulo 10^9 + 7.
Important Clarification
The paths (u, v) and (v, u) represent the same path and must be counted only once.
For example:
(1,2) == (2,1)
(1,2,3) == (3,2,1)
Single-node paths such as (1), (2), or (3) are not counted.


