minimum-cost-to-make-red-nodes-connected

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer <code>n</code> representing a tree with <code>n</code> nodes, where the nodes are numbered from 0 to <code>n - 1</code> and the tree is rooted at node 0. The tree is represented by a 2D array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [ui, vi]</code> indicates an undirected edge between nodes <code>ui</code> and <code>vi</code>.

You are also given a string <code>colors</code> of length <code>n</code>, where <code>colors[i]</code> represents the color of node <code>i</code>: <code>&#39;R&#39;</code> if it is Red, or <code>&#39;B&#39;</code> if it is Blue.

You may flip the color of any node: from <code>&#39;R&#39;</code> to <code>&#39;B&#39;</code>, or from <code>&#39;B&#39;</code> to <code>&#39;R&#39;</code>. Flipping node <code>u</code> incurs a cost equal to the size of the subtree of node <code>u</code>.

Your goal is to perform flips so the Red nodes form a single connected component in the tree. Blue nodes may be disconnected. A configuration with no Red nodes is also considered valid.

Return the minimum total cost required to achieve this.

In a rooted tree, the subtree of a node <code>v</code> is the set of all nodes whose path to the root contains <code>v</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 3, colors = &quot;RBR&quot;, edges = [[0,1],[1,2]]

Output: 1

Explanation:

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33714am.png" style="height: 60px; width: 237px;" />

<ul>
	<li>There are two Red nodes (0 and 2) that are not connected to each other.</li>
	<li>We can flip node 2 from <code>&#39;R&#39;</code> (Red) to <code>&#39;B&#39;</code> (Blue). The subtree size of node 2 is 1, so the cost is 1.</li>
	<li>After this flip only node 0 remains Red, forming exactly one connected Red component.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: n = 3, colors = &quot;RBR&quot;, edges = [[0,1],[0,2]]

Output: 0

Explanation:​​​​​​​

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33754am.png" style="width: 214px; height: 150px;" />

<ul>
	<li>There are two Red nodes (0 and 2) that are already connected to each other.</li>
	<li>No flips are needed since all Red nodes already form a single connected group. Thus, the minimum total cost is 0.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: n = 4, colors = &quot;BRRR&quot;, edges = [[0,1],[0,2],[0,3]]

Output: 2

Explanation:​​​​​​​

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33832am.png" style="width: 242px; height: 150px;" />

<ul>
	<li>There are three Red nodes (1, 2 and 3), which are not connected to each other.</li>
	<li>All three Red nodes are leaves and are disconnected from one another.</li>
	<li>To obtain a single Red group, we keep one Red leaf and flip the other two to Blue.</li>
	<li>Each leaf subtree size is 1, so flipping any two costs 2.</li>
</ul>
</div>

Example 4:

<div class="example-block">
Input: n = 3, colors = &quot;BBB&quot;, edges = [[0,1],[1,2]]

Output: 0

Explanation:

​​​​​​​<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33900am.png" style="width: 277px; height: 55px;" />

<ul>
	<li>All nodes are Blue, so there are no Red nodes.</li>
	<li>An empty Red group is considered a single connected group, so this state is already valid. Thus, the cost is 0.</li>
</ul>
</div>

&nbsp;
Constraints:​​​​​​​

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>n == colors.length</code></li>
	<li><code>colors[i]</code> is either <code>&#39;R&#39;</code> or <code>&#39;B&#39;</code>.</li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i] =&nbsp;[ui, vi]</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li>The input is generated such that <code>edges</code> represents a valid tree.</li>
</ul>

第 527 场周赛

weekly-contest-527

minCost

Minimum Cost to Make Red Nodes Connected

给你一个整数 <code>n</code>，表示一棵有 <code>n</code> 个节点的树，节点编号从 0 到 <code>n - 1</code>，并且树以节点 0 为&nbsp;根节点。这棵树由一个长度为 <code>n - 1</code> 的二维数组 <code>edges</code> 表示，其中 <code>edges[i] = [ui, vi]</code> 表示节点 <code>ui</code> 和 <code>vi</code> 之间存在一条&nbsp;无向&nbsp;边。

另给你一个长度为 <code>n</code> 的字符串 <code>colors</code>，其中 <code>colors[i]</code> 表示节点 <code>i</code> 的颜色：<code>'R'</code> 表示红色，<code>'B'</code> 表示蓝色。

你可以&nbsp;翻转&nbsp;任意节点的颜色：从 <code>'R'</code> 变为 <code>'B'</code>，或从 <code>'B'</code> 变为 <code>'R'</code>。翻转节点 <code>u</code> 的代价等于以节点 <code>u</code> 为根的子树的大小。

你的目标是通过翻转颜色，使所有&nbsp;红色&nbsp;节点在树中形成&nbsp;一个连通分量&nbsp;。蓝色节点可以不连通。没有红色节点的配置也视为有效。

返回实现这一目标所需的&nbsp;最小总代价&nbsp;。

在有根树中，节点 <code>v</code> 的子树是由所有到根节点的路径经过 <code>v</code> 的节点组成的集合。

&nbsp;

示例 1：

<div class="example-block">
输入： n = 3, colors = "RBR", edges = [[0,1],[1,2]]

输出： 1

解释：

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33714am.png" style="height: 60px; width: 237px;" />

<ul>
	<li>有两个红色节点（0 和 2），它们彼此不连通。</li>
	<li>可以将节点 2 从 <code>'R'</code>（红色）翻转为 <code>'B'</code>（蓝色）。节点 2 的子树大小为 1，因此代价为 1。</li>
	<li>翻转后，只有节点 0 仍为红色，恰好形成一个红色连通分量。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： n = 3, colors = "RBR", edges = [[0,1],[0,2]]

输出： 0

解释：​​​​​​​

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33754am.png" style="width: 214px; height: 150px;" />

<ul>
	<li>有两个红色节点（0 和 2），它们已经彼此连通。</li>
	<li>所有红色节点已经形成一个连通分量，因此无须翻转。最小总代价为 0。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： n = 4, colors = "BRRR", edges = [[0,1],[0,2],[0,3]]

输出： 2

解释：​​​​​​​

<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33832am.png" style="width: 242px; height: 150px;" />

<ul>
	<li>有三个红色节点（1、2 和 3），它们彼此不连通。</li>
	<li>这三个红色节点都是叶节点，且互不连通。</li>
	<li>为了得到一个红色连通分量，保留一个红色叶节点，并将另外两个翻转为蓝色。</li>
	<li>每个叶节点的子树大小均为 1，因此翻转其中任意两个的总代价为 2。</li>
</ul>
</div>

示例 4：

<div class="example-block">
输入： n = 3, colors = "BBB", edges = [[0,1],[1,2]]

输出： 0

解释：

​​​​​​​<img src="https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33900am.png" style="width: 277px; height: 55px;" />

<ul>
	<li>所有节点均为蓝色，因此没有红色节点。</li>
	<li>空的红色节点集合也视为一个连通分量，因此当前状态已经有效，代价为 0。</li>
</ul>
</div>

&nbsp;

提示：​​​​​​​

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>n == colors.length</code></li>
	<li><code>colors[i]</code> 为 <code>'R'</code> 或 <code>'B'</code>。</li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i] =&nbsp;[ui, vi]</code></li>
	<li><code>0 &lt;= ui, vi &lt;= n - 1</code></li>
	<li>输入保证 <code>edges</code> 表示一棵有效的树。</li>
</ul>

使红色节点连通的最小代价

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个整数 n，表示一棵有 n 个节点的树，节点编号从 0 到 n - 1，并且树以节点 0 为 根节点。这棵树由一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间存在一条 无向 边。

另给你一个长度为 n 的字符串 colors，其中 colors[i] 表示节点 i 的颜色：'R' 表示红色，'B' 表示蓝色。

你可以 翻转 任意节点的颜色：从 'R' 变为 'B'，或从 'B' 变为 'R'。翻转节点 u 的代价等于以节点 u 为根的子树的大小。

你的目标是通过翻转颜色，使所有 红色 节点在树中形成 一个连通分量 。蓝色节点可以不连通。没有红色节点的配置也视为有效。

返回实现这一目标所需的 最小总代价 。

在有根树中，节点 v 的子树是由所有到根节点的路径经过 v 的节点组成的集合。

 

示例 1：

输入： n = 3, colors = "RBR", edges = [[0,1],[1,2]]

输出： 1

解释：

[https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33714am.png]

 * 有两个红色节点（0 和 2），它们彼此不连通。
 * 可以将节点 2 从 'R'（红色）翻转为 'B'（蓝色）。节点 2 的子树大小为 1，因此代价为 1。
 * 翻转后，只有节点 0 仍为红色，恰好形成一个红色连通分量。

示例 2：

输入： n = 3, colors = "RBR", edges = [[0,1],[0,2]]

输出： 0

解释：

[https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33754am.png]

 * 有两个红色节点（0 和 2），它们已经彼此连通。
 * 所有红色节点已经形成一个连通分量，因此无须翻转。最小总代价为 0。

示例 3：

输入： n = 4, colors = "BRRR", edges = [[0,1],[0,2],[0,3]]

输出： 2

解释：

[https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33832am.png]

 * 有三个红色节点（1、2 和 3），它们彼此不连通。
 * 这三个红色节点都是叶节点，且互不连通。
 * 为了得到一个红色连通分量，保留一个红色叶节点，并将另外两个翻转为蓝色。
 * 每个叶节点的子树大小均为 1，因此翻转其中任意两个的总代价为 2。

示例 4：

输入： n = 3, colors = "BBB", edges = [[0,1],[1,2]]

输出： 0

解释：

[https://assets.leetcode.com/uploads/2026/07/10/screenshot-2026-07-11-at-33900am.png]

 * 所有节点均为蓝色，因此没有红色节点。
 * 空的红色节点集合也视为一个连通分量，因此当前状态已经有效，代价为 0。

 

提示：

 * 1 <= n <= 105
 * n == colors.length
 * colors[i] 为 'R' 或 'B'。
 * edges.length == n - 1
 * edges[i] = [ui, vi]
 * 0 <= ui, vi <= n - 1
 * 输入保证 edges 表示一棵有效的树。