Potential Tree

★★★★★

2 votes

Depth First Search, Algorithms, Graphs

Details

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:-

Rooted at 0

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]$ .