#3338. tree
DE_aemmprty
·
·
个人记录
有一个 n 个节点的树，每个节点上有一个颜色 a_i，令 f_{i, j} 表示节点 i 到节点 j 的路径上所有点的不同颜色数量。现在给你一个 n\times n 的二维数组，请你找到一个树和一个颜色方案能得到输入的 f 数组，保证有解。
\mathbf{Preperation}
这题可能是怎么做的。
- 观察部分分，有只考虑链的情况。我们可以先不考虑树的结构，只单纯思考颜色的构造。
- 当颜色数特别少的时候，如何构造？
\mathbf{Lemma}
:::warning[\mathbf{Lemma. 1}]{open}
如果一个 x 能通过同一个点权到达 S，那么对于所有 x, y \in S，都有 f_{x, y} = 1。
推论：不存在 x \in S, y \notin S，f_{x, y} = 1。
:::
:::warning[\mathbf{Lemma. 2}]{open}
对于两个同色集合 A, B，有所有 x \in A, y \in B，f_{x, y} 都相等。
:::
\mathbf{Question. 1}
颜色数最多两种时，如何构造？
::::info[\mathbf{ANSWER}]{open}
先随便选一个点 x，那么与 x 相连的点集被分为 A, B，其中 A 是一种，B 是两种。
我们先拉出若干条边权为 $1$ 的链，再用 $2$ 连起来即可。
::::
### $\mathbf{Question. 2}
当存在链的解时，如何构造？
:::error[\mathbf{Mistake}]
场上没看到 i \to i + 1，导致被误导，认为每次还要特地去寻找新的结点，并判定是否能接到链的末尾。
还是实力问题！
:::
:::info[\mathbf{ANSWER}]{open}
假设我们已经求出了 1 到 x 的颜色是什么，现在要加入第 x + 1 个点。
考虑 f_{i, x} 和 f_{i, x + 1}。如果这两个数相等，说明 c_{x + 1} 在 [i, x] 中出现过了，否则就是没出现过。
我们找到最后一个 i，使得 f_{i, x} = f_{i, x + 1}，那么，由于 c_{x + 1} 在 [i, x] 出现而不在 [i + 1, x] 出现，我们有 c_i = c_x。
如果全部都不相等，就设 c_{x + 1} = x + 1。若有解那么这一定是可行的。
:::
\mathbf{Question. 3}
::::info[$\mathbf{ANSWER}$]{open}
我们考虑将链上的做法放到树上。
假设我们当前考虑到 $v$，然后我们要找到一个 $f_{i, u} = f_{i, v}$ 且 $f_{i', u} \neq f_{i', v}$，这时一定有 $c_v = c_i$。
对于这个，我们枚举 $u, v$，然后从 $u$ 开始 DFS，如果遇到了合法的 $i$，就不往下 DFS 了。
::::
### $\mathbf{Question. 4}
如何找到一个合法的树？
::::info[\mathbf{ANSWER}]{open}
如果 f_{u, v} = 1，由 \mathbf{Lemma. 1 / 2}，我们可以把他们压起来。因此，我们可以默认 f_{u, v} > 1。
首先，一条合法的树边 u \to v，f_{u, v} 肯定为 2。但是可能有很多的 f_{u, v} = 2，所以似乎不知道要选哪一些边。
现在，有结论：原题存在解等价于对于任意一个 f_{u, v} = 2 的 (u, v) 组成的生成树，该树存在解。
:::warning[\mathbf{Prove}(感性理解)]{open}
我们观察 f_{u, v} = 2 的 (u, v) 点对。实际上，如果有一个 f_{u, v} = 2，那在 u 到 v 的路径上的任意两个点 x, y，都有 f_{x, y} = 2。
也就是说，这个图实际上是若干个团连接在了一起，如下图：
因此，每个团之间是互相独立的。我们单独考虑每个团，假设团的点集为 S，该团的两种点权分别是 a, b。
我们考虑所有 x 向 y 的经过 S 的路径，这时有两种可能：
- 只经过了 S 中的一个点 t，这时经过的边一定与该团无关，与 c_t 有关
- 经过了 S 中的一条边，这时路径只与该团的两种权值 a, b 有关
因此，其实对于一个团内的连边方式并不重要，我们任取一个生成树即可。
:::
通过这个结论，我们可以随便找一颗 f_{u, v} = 2 的生成树，然后跑 \mathbf{Question. 3} 的染色方法即可。
::::