3331. Find Subtree Sizes After Changes Medium

1/**
2 * [3331] Find Subtree Sizes After Changes
3 *
4 * You are given a tree rooted at node 0 that consists of n nodes numbered from 0 to n - 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.
5 * You are also given a string s of length n, where s[i] is the character assigned to node i.
6 * We make the following changes on the tree one time simultaneously for all nodes x from 1 to n - 1:
7 * 
8 * 	Find the closest node y to node x such that y is an ancestor of x, and s[x] == s[y].
9 * 	If node y does not exist, do nothing.
10 * 	Otherwise, remove the edge between x and its current parent and make node y the new parent of x by adding an edge between them.
11 * 
12 * Return an array answer of size n where answer[i] is the size of the <span data-keyword="subtree">subtree</span> rooted at node i in the final tree.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">parent = [-1,0,0,1,1,1], s = "abaabc"</span>
17 * Output: <span class="example-io">[6,3,1,1,1,1]</span>
18 * Explanation:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2024/08/15/graphex1drawio.png" style="width: 230px; height: 277px;" />
20 * The parent of node 3 will change from node 1 to node 0.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">parent = [-1,0,4,0,1], s = "abbba"</span>
25 * Output: <span class="example-io">[5,2,1,1,1]</span>
26 * Explanation:
27 * <img alt="" src="https://assets.leetcode.com/uploads/2024/08/20/exgraph2drawio.png" style="width: 160px; height: 308px;" />
28 * The following changes will happen at the same time:
29 * 
30 * 	The parent of node 4 will change from node 1 to node 0.
31 * 	The parent of node 2 will change from node 4 to node 1.
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	n == parent.length == s.length
37 * 	1 <= n <= 10^5
38 * 	0 <= parent[i] <= n - 1 for all i >= 1.
39 * 	parent[0] == -1
40 * 	parent represents a valid tree.
41 * 	s consists only of lowercase English letters.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/find-subtree-sizes-after-changes/
47// discuss: https://leetcode.com/problems/find-subtree-sizes-after-changes/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn find_subtree_sizes(parent: Vec<i32>, s: String) -> Vec<i32> {
53        vec![]
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_3331() {
65    }
66}
67