n nodes numbered 0 to n − 1, rooted at node 0. The list links holds its n − 1 edges: a pair [a, b] means nodes a and b are connected (the pair says nothing about direction). Every node carries a mark, a lowercase English letter: node i is marked marks[i].
The subtree of a node v is v itself together with all of its descendants, as seen from the root. For each node v, count how many nodes in its subtree carry the same mark as v (including v).
Return a list of length n whose i-th element is the count for node i.n=5, links=[[0, 1], [0, 2], [2, 3], [2, 4]], marks="xyxxy" → [3, 1, 2, 1, 1]
The subtree of node 0 (mark x) holds all five nodes, and nodes 0, 2 and 3 are marked x, so the answer is 3. The subtree of node 2 holds nodes 2, 3 and 4, of which 2 and 3 are marked x, giving 2. Every other node has only itself in its subtree.
n=3, links=[[1, 0], [2, 1]], marks="qqq" → [3, 2, 1]
The tree is the chain 0 – 1 – 2 rooted at 0. All marks are the same, so the answer is just the subtree sizes.
n=1, links=[], marks="k" → [1]
marks consists of lowercase English lettersn=5, links=[[0, 1], [0, 2], [2, 3], [2, 4]], marks="xyxxy"
[3, 1, 2, 1, 1]
Run checks the first 3 tests in your browser. Submit checks all 32 tests on the server, hidden ones included.