P15709 [JAG 2023 Summer Camp #2] Gemini Tree (Ver.Jadeite)

考虑一棵树，每个顶点上放置了一颗绿色或蓝色的石头。如果在执行以下操作 1 和 2 后能够满足条件 3，则称这样的树为“双子树”。 1. 首先，进行“选择由边直接连接的顶点对，并交换放置在每个端点上的石头”这一操作，可以进行零次或多次。 2. 其次，选择至多一条边并将其删除。 3. 此时，树被分割成至多两个连通分量，并且每个分量中只放置了一种颜色的石头。 考虑一棵每条边都有指定长度的“双子树”，并按如下方式定义其价值。 1. 首先，进行“选择由边直接连接的顶点对，并交换放置在每个端点上的石头”这一操作，可以进行零次或多次。每次交换操作的成本等于该边的长度。 2. 其次，选择至多一条边并将其删除。 3. 此时，树被分割成至多两个连通分量，并且每个分量中只放置了一种颜色的石头。 4. 为达成条件 3 所需的操作 1 的总成本的最小值，即为该“双子树”的价值。 注意，在计算价值时，石头本身不被移动。 你被给定一棵每条边都有指定长度的“双子树”。它有 $N$ 个顶点，其中 $N$ 是奇数。第 $i$ 条边连接两个顶点 $u_i$ 和 $v_i$，长度为 $w_i$。放置在顶点上的石头颜色由字符串 $S = s_1s_2 \ldots s_N$ 表示。 你将对这棵树依次执行 $Q$ 次操作。第 $j$ 次操作由两个整数 $e_j, a_j$ 定义，表示将第 $e_j$ 条边的长度增加 $a_j$。该操作的效果在后续操作中依然保持。请回答每次操作后树的价值。

$$ \begin{aligned} & N \\ & s_1s_2 \ldots s_N \\ & u_1 \ v_1 \ w_1 \\ & \vdots \\ & u_{N-1} \ v_{N-1} \ w_{N-1} \\ & Q \\ & e_1 \ a_1 \\ & \vdots \\ & e_Q \ a_Q \end{aligned} $$ 输入满足以下约束： - 所有输入均为整数。 - $3 \leq N \leq 10^5$ - $N$ 是奇数。 - $s_i$ 是“G”或“B”，表示顶点 $i$ 上石头的颜色。“G”代表绿色，“B”代表蓝色。 - $1 \leq u_i, v_i \leq N$ - $0 \leq w_i \leq 10^5$ - 给定的图满足“双子树”的条件。 - $1 \leq Q \leq 10^5$ - $1 \leq e_j \leq N - 1$ - $1 \leq a_j \leq 10^5$

输出 $Q$ 行答案。在第 $j$ 行，输出第 $j$ 次操作后树的价值。每行末尾请添加换行符。

在样例输入 1 中，只有一颗绿色石头。因此，问题是以最小成本将其移动到其中一个叶子节点。 翻译由 DeepSeek V3.2 完成