find-subtree-sizes-after-changes

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a tree rooted at node 0 that consists of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code>. The tree is represented by an array <code>parent</code> of size <code>n</code>, where <code>parent[i]</code> is the parent of node <code>i</code>. Since node 0 is the root, <code>parent[0] == -1</code>.

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

We make the following changes on the tree one time simultaneously for all nodes <code>x</code> from <code>1</code> to <code>n - 1</code>:

<ul>
	<li>Find the closest node <code>y</code> to node <code>x</code> such that <code>y</code> is an ancestor of <code>x</code>, and <code>s[x] == s[y]</code>.</li>
	<li>If node <code>y</code> does not exist, do nothing.</li>
	<li>Otherwise, remove the edge between <code>x</code> and its current parent and make node <code>y</code> the new parent of <code>x</code> by adding an edge between them.</li>
</ul>

Return an array <code>answer</code> of size <code>n</code> where <code>answer[i]</code> is the size of the subtree rooted at node <code>i</code> in the final tree.

&nbsp;
Example 1:

<div class="example-block">
Input: parent = [-1,0,0,1,1,1], s = &quot;abaabc&quot;

Output: [6,3,1,1,1,1]

Explanation:
<img alt="" src="https://assets.leetcode.com/uploads/2024/08/15/graphex1drawio.png" style="width: 230px; height: 277px;" />
The parent of node 3 will change from node 1 to node 0.
</div>

Example 2:

<div class="example-block">
Input: parent = [-1,0,4,0,1], s = &quot;abbba&quot;

Output: [5,2,1,1,1]

Explanation:
<img alt="" src="https://assets.leetcode.com/uploads/2024/08/20/exgraph2drawio.png" style="width: 160px; height: 308px;" />
The following changes will happen at the same time:

<ul>
	<li>The parent of node 4 will change from node 1 to node 0.</li>
	<li>The parent of node 2 will change from node 4 to node 1.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == parent.length == s.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= parent[i] &lt;= n - 1</code> for all <code>i &gt;= 1</code>.</li>
	<li><code>parent[0] == -1</code></li>
	<li><code>parent</code> represents a valid tree.</li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

findSubtreeSizes

Find Subtree Sizes After Changes

Tree

Depth-First Search

Array

Hash Table

String

给你一棵 <code>n</code>&nbsp;个节点且根节点为编号 0 的树，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。这棵树用一个长度为&nbsp;<code>n</code>&nbsp;的数组&nbsp;<code>parent</code>&nbsp;表示，其中&nbsp;<code>parent[i]</code>&nbsp;是第 <code>i</code>&nbsp;个节点的父亲节点的编号。由于节点 0 是根，<code>parent[0] == -1</code>&nbsp;。

给你一个长度为 <code>n</code>&nbsp;的字符串&nbsp;<code>s</code>&nbsp;，其中&nbsp;<code>s[i]</code>&nbsp;是节点 <code>i</code>&nbsp;对应的字符。

对于节点编号从 <code>1</code>&nbsp;到 <code>n - 1</code>&nbsp;的每个节点 <code>x</code>&nbsp;，我们 同时 执行以下操作 一次&nbsp;：

<ul>
	<li>找到距离节点 <code>x</code>&nbsp;最近&nbsp;的祖先节点 <code>y</code>&nbsp;，且&nbsp;<code>s[x] == s[y]</code>&nbsp;。</li>
	<li>如果节点 <code>y</code>&nbsp;不存在，那么不做任何修改。</li>
	<li>否则，将节点 <code>x</code>&nbsp;与它父亲节点之间的边 删除&nbsp;，在 <code>x</code>&nbsp;与 <code>y</code>&nbsp;之间连接一条边，使&nbsp;<code>y</code>&nbsp;变为 <code>x</code>&nbsp;新的父节点。</li>
</ul>

请你返回一个长度为 <code>n</code>&nbsp;的数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是 最终&nbsp;树中，节点 <code>i</code>&nbsp;为根的 子树 的 大小&nbsp;。

&nbsp;

示例 1：

<div class="example-block">
输入：parent = [-1,0,0,1,1,1], s = "abaabc"

输出：[6,3,1,1,1,1]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/08/15/graphex1drawio.png" style="width: 230px; height: 277px;" />

节点 3 的父节点从节点 1 变为节点 0 。
</div>

示例 2：

<div class="example-block">
输入：parent = [-1,0,4,0,1], s = "abbba"

输出：[5,2,1,1,1]

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/08/20/exgraph2drawio.png" style="width: 160px; height: 308px;" />

以下变化会同时发生：

<ul>
	<li>节点 4 的父节点从节点 1 变为节点 0 。</li>
	<li>节点 2 的父节点从节点 4 变为节点 1 。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>n == parent.length == s.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li>对于所有的&nbsp;<code>i &gt;= 1</code>&nbsp;，都有&nbsp;<code>0 &lt;= parent[i] &lt;= n - 1</code>&nbsp;。</li>
	<li><code>parent[0] == -1</code></li>
	<li><code>parent</code>&nbsp;表示一棵合法的树。</li>
	<li><code>s</code>&nbsp;只包含小写英文字母。</li>
</ul>