题目大意

给定一棵 $n$ 个节点的树，每个节点可以染成颜色 $0$ 或 $1$。对于树上的一条路径 $(u,v)$（包含端点），定义其价值为路径上所有节点颜色的 MEX（最小缺失非负整数）。一种染色方案的总价值为所有满足 $1 \le u \le v \le n$ 的路径价值之和。求最大可能的总价值。

思路分析

首先转换问题：对于一条路径，颜色的 MEX 最大只能为 $2$（因为只有 $0$ 和 $1$ 两种颜色）。树中路径总数为 $\frac{n(n+1)}{2}$，因此所有路径 MEX 之和的最大可能值是

$$\text{MAX} = 2 \times \frac{n(n+1)}{2} = n(n+1).$$

对于任意一种染色，定义每条路径的损失为 $2 - \text{MEX}$，则总价值可以表示为

$$\text{总价值} = n(n+1) - \text{总损失}.$$

于是原问题转化为：最小化所有路径的损失之和。

考虑一条路径的损失：

• 若路径上同时有 $0$ 和 $1$，MEX $=2$，损失 $=0$；
• 若路径上只有 $0$，MEX $=1$，损失 $=1$；
• 若路径上只有 $1$，MEX $=0$，损失 $=2$。

可以发现，只有两端点在同色连通块内的路径才会产生非零损失。具体来说，对于树上的一个全为 $0$ 的连通块，大小为 $k$，其内部所有路径的损失之和为 $\frac{k(k+1)}{2} \times 1$；对于全为 $1$ 的连通块，内部每条路径损失为 $2$，因此损失之和为 $\frac{k(k+1)}{2} \times 2 = k(k+1)$。

可以证明，在最优染色中，最大同色连通块的大小 $k$ 满足

$$\frac{k(k+1)}{2} \le 2n \quad \Rightarrow \quad k = O(\sqrt{n}). $$

当 $n \le 2\times 10^5$ 时，$k$ 的实际最大值不超过 $258$，代码中取上界 $lim = 893$ 足以保证正确性。

基于此，我们可以设计一个树上背包动态规划。

动态规划状态

设 $dp_{u,0,j}$ 表示在以 $u$ 为根的子树中，节点 $u$ 染成颜色 $0$，且 $u$ 所在的全 $0$ 连通块大小为 $j$ 时，子树内部的最小损失。

类似地，$dp_{u,1,j}$ 表示 $u$ 染成颜色 $1$，所在全 $1$ 连通块大小为 $j$ 时的最小损失。

转移

初始化：对于单个节点 $u$，

• 若染成 $0$，大小为 $1$，损失为 $1$（单点路径只有颜色 $0$，MEX $=1$，损失 $=1$）；
• 若染成 $1$，大小为 $1$，损失为 $2$（单点路径只有颜色 $1$，MEX $=0$，损失 $=2$）。

即

$$dp_{u,0}[1] = 1,\quad dp_{u,1}[1] = 2.$$

然后依次合并子节点 $v$。假设当前已合并的部分中 $u$ 的连通块大小为 $j$，子节点 $v$ 返回的状态中连通块大小为 $l$，分两种情况讨论：

1. 颜色不同（$u$ 与 $v$ 异色）
   $u$ 的连通块不会扩展，两个连通块之间跨子树的路径必然同时包含 $0$ 和 $1$，损失为 $0$。总损失直接相加：

   • $u$ 为 $0$、$v$ 为 $1$：$dp_{u,0}[j] + dp_{v,1}[l]$
   • $u$ 为 $1$、$v$ 为 $0$：$dp_{u,1}[j] + dp_{v,0}[l]$

2. 颜色相同
   此时两个连通块合并，大小变为 $j+l$。此外，原来分属两个连通块的节点之间会形成 $j \times l$ 条新路径，这些路径全部是同色的，因此每条路径会产生额外的损失。若都是 $0$，每条损失 $1$；若都是 $1$，每条损失 $2$。转移方程为：

   • 同色 $0$：$$dp_{u,0}[j+l] \gets \min\left(dp_{u,0}[j+l],\; dp_{u,0}[j] + dp_{v,0}[l] + j \times l \right) $$
   • 同色 $1$：$$dp_{u,1}[j+l] \gets \min\left(dp_{u,1}[j+l],\; dp_{u,1}[j] + dp_{v,1}[l] + 2 \times j \times l \right) $$

转移时使用临时数组记录合并后的结果，再复制回原状态。由于连通块大小上限为 $O(\sqrt{n})$，整个过程的时间复杂度为 $O(n\sqrt{n})$。

内存优化

直接开 $n \times \sqrt{n}$ 的 DP 数组会超内存。标程使用了动态大小的 vector，并限制每个状态只存储到当前子树大小与 $lim$ 的最小值，从而将空间降至线性。

最终答案

遍历根节点（$1$）的 DP 状态，取所有可能连通块大小下的最小损失：

$$ans = \min_{1 \le j \le lim} \min(dp_{1,0}[j],\; dp_{1,1}[j]). $$

最大总价值即为

$$n(n+1) - ans.$$

代码实现要点

• 先用一次 DFS 将每个节点的重儿子交换到子节点列表的首位，便于转移。
• $lim$ 取 $893$，超过该大小的连通块不会是最优解，可直接截断。
• 背包合并时注意枚举顺序，使用临时数组 merged 避免状态覆盖冲突。

复杂度分析

• 时间复杂度：$O(n \cdot lim) = O(n\sqrt{n})$。
• 空间复杂度：$O(n + lim)$，可以接受。

参考代码（C++）

见题目描述中的标准程序。