题目重述

有 $n$ 个块，每个块形如 $[c_1 \mid v \mid c_2]$，可以翻转。
要求选出一个子集并排序，使得相邻块接触端颜色相同，最大化选出的块的价值总和。

---

问题转化

将 $4$ 种颜色看作图的 $4$ 个节点，编号 $1,2,3,4$。

• 每个块 $[c_1 \mid v \mid c_2]$ 转化为一条 无向边，连接节点 $c_1$ 和 $c_2$，边权为 $v$。
• 翻转块相当于无向边的方向无关性。

一个 合法序列 对应图中一条 路径（可能重复经过节点），且每条边最多使用一次。
序列的价值 = 路径上所有边的权值和。

因此问题等价为：

在 $4$ 个节点的无向多重图中，找出一条 边权和最大 的路径（边不重复使用）。

---

转化为欧拉路径问题

在一个无向图中，如果一条路径 经过所有边恰好一次，则它是欧拉路径。
这里我们不要求经过所有边，而是选一个边集，使其构成一条路径。

对于选出的边集，如果它构成一条路径，则：

• 该边集在图上形成一条 连通 的边集；
• 该边集中，度数为奇数的顶点个数为 $0$ 或 $2$。

这正是 欧拉路径存在条件。

因此问题变为：

从所有边中选出一个子集，使得该子集连通且奇点数为 $0$ 或 $2$，并最大化边权和。

---

关键观察

1. 边类型有限

因为颜色只有 $4$ 种，所以 无向边类型 只有：

$$\binom{4}{2} + 4 = 6 + 4 = 10$$

但这里为了位掩码方便，通常按 有序对 处理，共 $4 \times 4 = 16$ 种（包括 $i \to j$ 和 $j \to i$ 分开）。
不过本题中是无向边，所以实际不同颜色对只有 $10$ 种，但实现时常按 $16$ 种统一处理。

2. 每种边最多移除一条

假设节点 $A$ 和 $B$ 之间有 $2x + y$ 条边，其中 $y \in \{0, 1\}$。
我们可以用 $x$ 次“来回”走这些边，这样不影响路径的起点和终点，且能使用其中 $2x$ 条边。
剩下的 $y$ 条边（$0$ 或 $1$ 条）如果会破坏奇偶性条件，才需要考虑移除。

因此，对于每一种颜色对 $(A, B)$，在构造最终路径时，最多有 一条边 被丢弃（如果存在多余边破坏奇偶性）。
并且，如果必须丢弃，我们会丢弃 价值最小 的那条边，以最大化总和。

---

算法设计

由于只有 $4$ 个节点，不同颜色对最多 $10$ 种（或 $16$ 种），我们可以 枚举哪些颜色对中丢弃一条边。

状态表示

用位掩码 $mask$ 表示哪些 边类型 被标记为“要移除一条边”。

• 共有 $16$ 种边类型（有序对），所以 $mask$ 范围 $0$ 到 $2^{16}-1$。
• 如果某类型在 $mask$ 中为 $1$，表示我们将从该类型中移除 价值最小 的一条边（如果该类型存在边）。

可行性判断

对于每个 $mask$：

1. 检查是否每种要移除的类型确实存在边，否则跳过。
2. 计算移除的总价值：$$\text{removed\_sum} = \sum_{\text{type in mask}} \text{mn}[type] $$其中 $\text{mn}[type]$ 是该类型边的最小价值。
3. 剩余边集为：
   • 若某类型在 $mask$ 中，则保留该类型除最小边外的所有边；
   • 否则保留该类型全部边。
4. 检查剩余边集是否满足 欧拉路径条件：
   • 连通性（有边存在的节点必须连通）；
   • 度数为奇数的顶点数为 $0$ 或 $2$。

若满足，则候选答案为：

$$\text{total\_sum} - \text{removed\_sum}$$

取所有可行 $mask$ 的最大值。

特殊情况

如果所有边都无法构成长度 ≥ 2 的路径，答案也可以是 单条边的最大值。
因此最后与 $\text{single\_max}$ 取 $\max$。

---

复杂度分析

• 枚举 $mask$：$2^{16} = 65536$ 种。
• 对每个 $mask$ 进行连通性、度数检查：$O(1)$（因为只有 4 个节点）。
• 预处理每种类型的边数、总价值和最小价值：$O(n)$。

总复杂度：

$$O(2^{16} \times 4^2 + n) = O(2^{16} \times 16 + n) \approx O(2^{16} \times n) $$

实际实现中 $n \le 100$，完全可行。

---

代码实现要点

• 用 $cnt[a][b]$ 记录颜色对 $(a,b)$ 的边数（无向，$a \le b$）。
• 用 $sum[a][b]$ 记录总价值。
• 用 $mn[a][b]$ 记录最小价值。
• 位掩码索引计算：
  对于颜色 $i, j$（$1 \le i,j \le 4$），索引为 $(i-1)\times 4 + (j-1)$。
• 连通性检查：并查集。
• 度数计算：对保留的边类型累加度数（自环贡献 $2$ 度）。

---

扩展思考（Bonus）

$O(n^2)$ 做法

可以用 DP 或最大权路径的状压 DP，因为节点数极少（4 个），但边数 $n$ 较大时仍可做到 $O(n \cdot 2^4)$ 或 $O(n^2)$，但本题 $n \le 100$，位掩码法已足够。

$O(n)$ 做法

理论上有更巧妙的结论：因为颜色少，最终路径的形态有限，可以通过分类讨论直接计算最优值，但实现较复杂，且常数小的情况下 $O(2^{16} \times n)$ 已是高效解法。

---

总结

本题的核心是将块序列问题转化为 图论中的最大权欧拉路径问题，利用颜色数量少（4）的性质，通过 枚举哪些边类型丢弃一条边 来构造合法边集，并检查欧拉路径条件，从而在 $O(2^{16} \times n)$ 时间内求解。