Tap here to switch tabs
Problem
Submissions

Problem: Find Subtree Sizes After Changes

Try to solve the Find Subtree Sizes After Changes problem.

Statement

You are given a tree consisting of nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by an integer array parent of length nn, where parent[i] is the parent of node i, and parent[0] == -1. You are also given a string s of length nn, where s[i] represents the character assigned to node i.

You need to modify the tree by updating the parent of each node:
For every node i from 11 to n−1n - 1, find the closest ancestor ancestor such that s[i] == s[ancestor]. If such an ancestor exists, update the parent of node i to ancestor. All updates are performed simultaneously.

Return an array ans of length nn, where ans[i] is the number of nodes in the subtree rooted at node i in the modified tree.

Constraints:

  • n == parent.length == s.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq parent[i] ≤n−1\leq n - 1 for all i ≥1\geq 1

  • parent[0] == -1

  • parent represents a valid tree.

  • s consists only of lowercase English letters.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Subtree Sizes After Changes

Try to solve the Find Subtree Sizes After Changes problem.

Statement

You are given a tree consisting of nn nodes numbered from 00 to n−1n - 1, rooted at node 00. The tree is represented by an integer array parent of length nn, where parent[i] is the parent of node i, and parent[0] == -1. You are also given a string s of length nn, where s[i] represents the character assigned to node i.

You need to modify the tree by updating the parent of each node:
For every node i from 11 to n−1n - 1, find the closest ancestor ancestor such that s[i] == s[ancestor]. If such an ancestor exists, update the parent of node i to ancestor. All updates are performed simultaneously.

Return an array ans of length nn, where ans[i] is the number of nodes in the subtree rooted at node i in the modified tree.

Constraints:

  • n == parent.length == s.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq parent[i] ≤n−1\leq n - 1 for all i ≥1\geq 1

  • parent[0] == -1

  • parent represents a valid tree.

  • s consists only of lowercase English letters.