#3331

Find Subtree Sizes After Changes

specialist · 830 · lc medium +31 · 54% accepted · 105 likes · top 46%

Description

You are given a tree rooted at node 0 with n nodes numbered 0 to n - 1. It is represented by an array parent of size n, where parent[i] is the parent of node i; node 0 is the root so parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Simultaneously for all nodes x from 1 to n - 1, perform the following:

- Find the nearest ancestor y of x such that s[x] == s[y].

- If no such y exists, do nothing.

- Otherwise, detach x from its current parent and attach it to y instead.

Return an array answer of size n where answer[i] is the subtree size rooted at node i in the resulting tree.

Code

1

2

3

class Solution:
    def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:

class Solution:
    def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]: