题意概述

给定一个 $N \times N$ 的矩阵 $D$，其中 $D[i][j]$ 表示树中节点 $i$ 到 $j$ 的路径上不同颜色的数量。
已知树有 $N$ 个节点，每个节点有颜色（颜色值在 $1$ 到 $N$ 之间）。
要求根据 $D$ 矩阵，构造一棵树并给节点染色，使得矩阵与构造的树匹配。
输入中还有一个参数 $T$，表示数据类型（对应不同的子任务约束）。

数据范围：$N \le 3000$。

---

基本性质分析

设树中节点 $u$ 到 $v$ 的路径上颜色集合大小为 $d(u,v)$。
矩阵 $D$ 满足：

• $d(u,u) = 1$（自己到自己的路径只有自己的颜色）
• $d(u,v) = d(v,u)$
• 对任意三点 $u,v,w$，如果 $w$ 在 $u$ 到 $v$ 的路径上，则 $d(u,v) = d(u,w) + d(w,v) - 1$（因为 $w$ 的颜色在两边都算了一次，重复计算一次）。

---

关键观察

对于任意两个节点 $u,v$，$d(u,v)$ 表示路径上颜色种类数。
如果 $u$ 和 $v$ 相邻（直接有边），那么 $d(u,v) = 1$ 当且仅当 $u$ 和 $v$ 颜色相同；否则 $d(u,v) = 2$（因为两种颜色）。

更一般地，如果 $u$ 和 $v$ 的最近公共祖先为 $w$，那么 $d(u,v) = d(u,w) + d(w,v) - 1$。

矩阵 $D$ 实际上给出了任意两点间路径颜色数的“距离”信息（但不是普通距离，因为颜色可能重复）。

---

构造思路

1. 确定一个根节点

可以任选一个节点作为根（比如节点 1）。
根据 $D[1][i]$ 可以知道从根到 $i$ 的路径上不同颜色数。
设 $c_i$ 表示节点 $i$ 的颜色。

---

2. 构建父子关系

考虑节点 $i$ 和 $j$，如果 $D[1][i] + D[1][j] - D[i][j] = 1$，那么路径 $(1,i)$ 和 $(1,j)$ 的颜色集合只相差一个颜色（可能是 $i$ 或 $j$ 的颜色不同）。
这可以用于判断父子或兄弟关系。

更系统的方法：
对每个节点 $i$（除根外），我们要找到它的父节点。
对于节点 $i$，考虑所有 $j \neq i$，如果 $D[1][j] = D[1][i] - 1$ 且 $D[i][j] = 2$，那么 $j$ 可能是 $i$ 的父节点候选（因为从根到 $i$ 比到 $j$ 多一个颜色，且 $i$ 和 $j$ 之间颜色不同，所以 $i$ 是 $j$ 的孩子且颜色与 $j$ 不同）。
但可能有多个候选，需要进一步判断。

---

3. 利用矩阵性质判断父子

引理：在树中，如果 $p$ 是 $q$ 的父节点，那么对于任意节点 $x$，有 [ D[q][x] = \begin{cases} D[p][x] & \text{如果 $x$ 在 $p$ 的子树外（包括 $p$）且 $c_q \neq c_p$ 时可能差1？} \end{cases} ] 实际上更精确：

• 如果 $c_q \neq c_p$，则 $D[q][x] = D[p][x] + 1$ 当 $x$ 不在 $p$ 到根路径上且 $c_q$ 不在 $p$ 到 $x$ 的颜色集合中；否则 $D[q][x] = D[p][x]$。
  这太复杂，不易直接使用。

---

更实用的方法：增量构造树

从单个节点（比如节点 1）开始，逐步加入其他节点。
维护当前已构建的树（是最终树的子图）。
每次加入一个节点 $i$ 时，需要确定它在当前树中的父节点。

如何找父节点？
对于当前树中的节点 $x$，计算 $D[i][x]$。
如果 $x$ 是 $i$ 的父节点，那么对于树中任意节点 $y$（除 $i$ 外），有 $D[i][y] = D[x][y] + \delta$，其中 $\delta = 0$ 或 $1$ 取决于 $c_i$ 是否在 $x$ 到 $y$ 的颜色集合中出现过。
可以枚举候选父节点 $x$，检查是否对大多数 $y$ 成立。

---

已知题解做法（简要）

实际上这是一个已知问题：给定“颜色距离矩阵”，重建树和染色。
标准解法（$O(N^2)$）：

1. 以节点 1 为根，计算 $depth[i] = D[1][i]$（表示从根到 $i$ 的路径颜色数）。
2. 按 $depth$ 从小到大处理节点（即 BFS 序）。
3. 对于节点 $i$，在已处理的节点中寻找父节点 $p$，使得对于所有已处理节点 $j$，有： [ D[i][j] = D[p][j] + \epsilon(i,p,j) ] 其中 $\epsilon(i,p,j) = 1$ 如果 $c_i$ 不在 $p$ 到 $j$ 的颜色集合中，否则为 0。
4. 为了判断 $c_i$，可以观察 $D[i][p]$：
   • 如果 $D[i][p] = 1$，则 $c_i = c_p$。
   • 如果 $D[i][p] = 2$，则 $c_i \neq c_p$，且 $c_i$ 是一个新颜色或与某个祖先颜色相同。
5. 确定 $c_i$ 时，需要检查与已处理节点颜色的一致性。

具体实现时，可以用并查集维护颜色相同的节点集合。

---

算法步骤（详细）

预处理

• 读入 $T, N, D$。
• 以节点 1 为根，设 $depth[i] = D[1][i]$。

主循环

按 $depth$ 升序处理节点（根节点已处理）。
对于每个节点 $i$：

• 在已处理节点集合中找到父节点候选 $p$，满足 $depth[p] = depth[i] - 1$ 且 $D[i][p] \le 2$。
• 实际上，如果 $depth[p] = depth[i] - 1$ 且 $D[i][p] = 1$，则 $c_i = c_p$；如果 $D[i][p] = 2$，则 $c_i \neq c_p$。
• 为了唯一确定 $p$，需要检查对于所有已处理节点 $j$，$D[i][j]$ 与 $D[p][j]$ 的关系是否一致。

确定父节点

定义 $diff(i,p,j) = D[i][j] - D[p][j]$。
对于正确的父节点 $p$，$diff(i,p,j)$ 只能是 0 或 1。
而且 $diff(i,p,j) = 1$ 当且仅当 $c_i$ 不在 $p$ 到 $j$ 的路径颜色集合中。
我们可以利用这一性质筛选 $p$：
选择 $p$ 使得对所有已处理 $j$，$diff(i,p,j) \in \{0,1\}$ 且模式一致。

确定颜色

• 如果 $D[i][p] = 1$，则 $c_i = c_p$。
• 如果 $D[i][p] = 2$，则 $c_i$ 是新的或与某个祖先颜色相同。
  为了确定具体颜色，可以找一个 $j$ 使得 $diff(i,p,j) = 0$（即 $c_i$ 在 $p$ 到 $j$ 路径上出现），那么 $c_i$ 就是这条路径上某个节点的颜色。
  可以通过检查 $D[i][j]$ 与 $D[p][j]$ 的关系推断。

输出

• 输出颜色数组 $c[1..N]$。
• 输出 $N-1$ 条边（构建的树边）。

---

复杂度

每个节点 $i$ 需要与所有已处理节点比较，总复杂度 $O(N^2)$，$N \le 3000$ 可过。

---

总结

本题是构造题，给定路径颜色数矩阵反推树结构和染色。
核心是利用矩阵的性质逐步确定父子关系和节点颜色。
关键点：

1. 以某个节点为根，按“深度”（颜色数）排序。
2. 增量构建树，对每个节点寻找父节点。
3. 利用 $D[i][j]$ 与 $D[父][j]$ 的差值判断颜色出现情况。
4. 确定节点颜色（相同或不同）。

实际实现时需要注意 $T$ 的特殊性质（链或矩阵值限制），可简化处理。