Company: Hackerearth_1nov
Difficulty: medium
Parent node Problem Description You are given a tree consisting of N vertices, rooted at the vertex 1. Each vertex consists of a lowercase alphabet as the node value. A vertex considers its nearest ancestor as a parent if the ancestor has the node value same as that of the vertex. Your task is to detach all the nodes and attach them to its valid parents and print the count of the number of nodes in the subtree of each node. Input format First line: T denoting the number of test cases Second line: N number of vertices in the given tree Third line: N space-separated lowercase alphabet where i th character denotes the value of the i th node Next N - 1 lines: Two integers U i and V i , meaning there is an edge between nodes U i and V i . Output format For each test case, print N space-separated integers in a new line, representing the count of the number of nodes in the subtree of i th node Examples Example 1: Input: 1 4 abab 1 2 2 3 2 4 Output: 2 2 1 1 Explanation: Two Trees are formed af