问题重述

我们有一个长度为 $2n$ 的合法括号序列 $s$，每个左括号有权值。目标是通过两种操作将 $s$ 变换为不包含 (A)(B) 这种不喜欢的结构，最小化代价。

操作说明：

• 操作 1：将 p(A)(B)q 变为 p(A()B)q，代价为 $x \times w_A + y \times w_B$
• 操作 2：将 pABq 变为 pBAq，代价为 $0$

其中 $w_A, w_B$ 分别是 (A) 和 (B) 的第一个左括号的权值。

---

关键观察

1. 括号序列的树结构

合法括号序列可以唯一对应一棵有根树：

• 每个括号对 (...) 对应树的一个节点
• 嵌套关系对应父子关系
• 并列关系 (...)(...) 对应兄弟关系

2. 不喜欢的结构 (A)(B)

在树结构中，(A)(B) 对应两个兄弟节点。也就是说，我们的目标是要消除所有具有多个子节点的节点（即度数 > 1 的节点）。

3. 操作的本质

• 操作 2（无代价交换）：可以任意重新排列兄弟节点的顺序
• 操作 1（有代价变换）：将两个兄弟节点 (A)(B) 合并为一个节点 (A()B)，即让其中一个成为另一个的子节点

---

问题转化

通过树结构的视角，原问题转化为：

给定一棵有根树，每个节点有一个权值（对应其第一个左括号的权值），我们可以：

1. 免费重新排列任何节点的子节点顺序
2. 花费 $x \times w_u + y \times w_v$ 的代价，将两个兄弟节点 $u, v$ 合并（让 $v$ 成为 $u$ 的子节点）

目标：通过合并操作，使得每个节点的度数不超过 1，最小化总代价。

---

核心解法

1. 树形 DP 状态设计

设 $dp[u]$ 表示处理完以 $u$ 为根的子树后，$u$ 的父节点需要额外支付的最小代价。

更准确地说：对于节点 $u$，如果它有多个子节点，我们必须通过操作 1 将它们合并成一条链。合并时需要选择哪个子节点作为链头，哪个作为链尾等。

2. 合并策略

考虑节点 $u$ 有 $k$ 个子节点 $v_1, v_2, \dots, v_k$：

• 通过操作 2，我们可以任意排列这些子节点
• 通过操作 1，我们将它们合并成一条链：$v_{i_1} \to v_{i_2} \to \dots \to v_{i_k}$

每次合并两个相邻节点 $v_i, v_j$ 的代价为：

• 如果 $v_i$ 在上，$v_j$ 在下：代价 = $x \times w_{v_i} + y \times w_{v_j}$
• 如果 $v_j$ 在上，$v_i$ 在下：代价 = $x \times w_{v_j} + y \times w_{v_i}$

3. 最优合并顺序

实际上，这是一个经典的链合并问题：

我们要将 $k$ 个节点合并成一条链，最小化总合并代价。每次合并的代价取决于两个节点的权值和参数 $x, y$。

关键结论：

• 当 $x = 0, y = 1$ 时：总是让权值小的节点作为被合并的节点（在下面）
• 当 $x = 1, y = 0$ 时：总是让权值小的节点作为主动合并的节点（在上面）
• 当 $x = 1, y = 1$ 时：合并顺序不影响总代价
• 当 $x = 0, y = 0$ 时：所有操作无代价

4. 算法框架

1. 建树：通过栈将括号序列转化为树结构
2. DFS：后序遍历树，对于每个节点 $u$：
   • 收集所有子节点的权值
   • 根据 $(x, y)$ 的值选择最优的合并策略
   • 计算合并的总代价，更新 $dp[u]$
3. 输出：根节点的 $dp$ 值即为答案

---

复杂度分析

• 建树：$O(n)$
• DFS 合并计算：每个节点处理其子节点列表，总复杂度 $O(n)$
• 总复杂度：$O(n)$，适合 $n \le 400000$ 的数据范围

---

特殊情况处理

1. $x = 0, y = 0$

所有操作无代价，答案为 $0$

2. 所有权值相等

合并顺序不影响，可以简化计算

3. 链状结构

如果原序列已经是 (((...))) 的形式，不需要任何操作

---

实现细节

1. 建树方法

stack = []
tree = [[] for _ in range(n+1)]
node_id = 0
for char in s:
    if char == '(':
        node_id += 1
        if stack:
            tree[stack[-1]].append(node_id)
        stack.append(node_id)
    else:
        stack.pop()

2. 合并代价计算

对于节点 $u$ 的子节点权值列表 $weights$：

• 如果 $x = 0, y = 1$：将 $weights$ 排序，代价 = $\sum_{i=2}^k weights[i]$（最小的 $k-1$ 个权值之和）
• 如果 $x = 1, y = 0$：代价 = $\sum_{i=1}^{k-1} weights[i]$（最大的 $k-1$ 个权值之和）
• 如果 $x = 1, y = 1$：代价 = $(\sum weights) + (k-2) \times \min(weights)$

---

总结

这道题的核心在于：

1. 括号序列到树的转化：理解 (A)(B) 和 (A()B) 在树结构中的含义
2. 操作语义分析：操作 2 允许任意重排，操作 1 进行节点合并
3. 贪心策略：根据 $(x, y)$ 的不同取值，采用不同的最优合并顺序
4. 树形 DP：自底向上计算合并代价

通过将括号序列问题转化为树上的链合并问题，再利用贪心策略最小化代价，最终得到了一个简洁高效的线性算法。