CF472D Design Tutorial: Inverse the Problem

有一种简单的方法可以从一个旧题目中获得一个新题目，叫做“反向题目”：我们给出原题的输出，然后要求构造一个输入，使得原题的解法能够产生我们给定的输出。Topcoder Open 2014 Round 2C 的难题 InverseRMQ 就是一个很好的例子。 现在让我们用这种方式创造一个新题目。我们将使用这样一道题目：给定一棵树，请计算任意两点间的距离。没错，这很简单，但它的反向版本要难一些：你现在给定一个 $n \times n$ 的距离矩阵，判断它是否是某棵加权树（所有权值都必须为正整数）的距离矩阵。

第一行包含一个整数 $n$（$1 ≤ n ≤ 2000$）——图中的点数。 接下来的 $n$ 行，每行包含 $n$ 个整数 $d_{i,j}$（$0 ≤ d_{i,j} ≤ 10^9$），表示节点 $i$ 到节点 $j$ 的距离。

如果存在这样的树，输出 "YES"；否则输出 "NO"。

有一种简单的方法可以从一个旧题目中获得一个新题目，叫做“反向题目”：我们给出原题的输出，然后要求构造一个输入，使得原题的解法能够产生我们给定的输出。Topcoder Open 2014 Round 2C 的难题 InverseRMQ 就是一个很好的例子。 现在让我们用这种方式创造一个新题目。我们将使用这样一道题目：给定一棵树，请计算任意两点间的距离。没错，这很简单，但它的反向版本要难一些：你现在给定一个 $n \times n$ 的距离矩阵，判断它是否是某棵加权树（所有权值都必须为正整数）的距离矩阵。 由 ChatGPT 5 翻译