Potential Tree
Problem
You are given a tree consisting of \(N\) vertices. Its root is not fixed yet. The \(potential\) of a non-leaf vertex is the count of its children (distance of \(1\) from the vertex) with a non-zero \(potential\). The \(potential\) of a leaf vertex \(i\) is \(i \% 2\).
Your task is to calculate the \(potential\) of every possible root. Find an array \(A\) such that \(A[i]\) represents the \(potential\) of vertex \(i\) if the tree was rooted at \(i\).
Input Format:
- The first line of input contains a single integer \(T\), denoting the number of test cases.
- The first line of each test case contains a single integer, \(N\), denoting the number of vertices.
- The following \(N-1\) lines contain two integers \(u,v\) denoting an edge between vertex \(u\) and vertex \(v\).
Output Format:
For each test case, print an array \(A\) such that \(A[i]\) represents the \(potential\) of vertex \(i\) if the tree was rooted at \(i\).
Constraints:
\(1 <= T <= 10\)
\(3 <= N <= 10^5\)
\(0 <= u, v < N\)
Time Limit: 4
Memory Limit: 256
Source Limit:
Explanation
First test case:-
- If the tree is rooted at vertex \(0\), vertex \(1, 3, 4\) are the leaf nodes, and the potential of vertex \(1, 3, 4\) are \(1, 1, 0\) respectively. Thus, the potential of vertex \(2\) is \(1\), and further, the potential of vertex \(0\) is \(2\).
- If the tree is rooted at vertex \(1\), vertices \(3\) and \(4\) are leaves, the potential of vertex \(3\) is \(1\), and vertex \(4\) is \(0\). The potential of vertex \(2\) is \(1\), potential of vertex \(0\) is \(1\). Thus, the potential of vertex \(1\) is \(1\)
- If the tree is rooted at vertex \(2\), vertex \(1, 3, 4\) are the leaves, and the potential of vertex \(1, 3, 4\) are \(1, 1, 0\) respectively. Thus, the potential of vertex \(0\) is \(1\), and further, the potential of vertex \(2\) is \(2\).
- If the tree is rooted at vertex \(3\), vertices \(4\) and \(1\) are leaves, the potential of vertex \(4\) is \(0\), and vertex \(1\) is \(1\). The potential of vertex \(0\) is \(1\), potential of vertex \(2\) is \(1\). Thus, the potential of vertex \(3\) is \(1\).
- If the tree is rooted at vertex \(4\), vertices \(1\) and \(3\) are leaves, the potential of vertex \(1\) is \(1\), and vertex \(3\) is \(1\). The potential of vertex \(0\) is \(1\), potential of vertex \(2\) is \(2\). Thus, the potential of vertex \(4\) is \(1\).
- Thus, the answer is \([2,1,2,1,1]\).
Second test case:-
- If the tree is rooted at vertex \(0\), vertex \(1\) is the only leaf, and the potential of vertex \(1\) is \(1\). Thus, the potential of vertex \(2\) is \(1\), and further, the potential of vertex \(0\) is \(1\).
- If the tree is rooted at vertex \(1\), vertex \(0\) is the only leaf, and the potential of vertex \(0\) is \(0\). Thus, the potential of vertex \(2\) is \(0\), and further, the potential of vertex \(1\) is \(0\).
- If the tree is rooted at vertex \(2\), vertices \(1\) and \(0\) are leaves, the potential of vertex \(1\) is \(1\), and vertex \(0\) is \(0\). Thus, the potential of vertex \(2\) is \(1\).
- Thus, the answer is \([1,0,1]\).
