CF472D.Design Tutorial: Inverse the Problem

There is an easy way to obtain a new task from an old one called "Inverse the problem": we give an output of the original task, and ask to generate an input, such that solution to the original problem will produce the output we provided. The hard task of Topcoder Open 2014 Round 2C, InverseRMQ, is a good example.

Now let's create a task this way. We will use the task: you are given a tree, please calculate the distance between any pair of its nodes. Yes, it is very easy, but the inverse version is a bit harder: you are given an n × n distance matrix. Determine if it is the distance matrix of a weighted tree (all weights must be positive integers).

有一种从旧题目生成新题目的简单方法，称为“逆向问题”：我们给出原题目的输出，然后要求构造一个输入，使得原题目的解法在该输入上运行后恰好产生我们所提供的输出。Topcoder Open 2014 Round 2C 中的难题 InverseRMQ 就是一个很好的例子。

现在我们用这种方法来构造一道新题。我们将基于如下题目出发：给你一棵树，请计算其任意两个节点之间的距离。是的，这非常简单；但其逆向版本则稍难一些：给你一个 $ n \times n $ 的距离矩阵，请判断它是否为某棵带权树的距离矩阵（所有边权必须为正整数）。

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of nodes in that graph.

Then next n lines each contains n integers d__i, j (0 ≤ d__i, j ≤ 109) — the distance between node i and node j.

第一行包含一个整数 $n$（$1 \leq n \leq 2000$）—— 图中节点的数量。

接下来的 $n$ 行，每行包含 $n$ 个整数 $d_{i,j}$（$0 \leq d_{i,j} \leq 10^9$）—— 节点 $i$ 与节点 $j$ 之间的距离。

If there exists such a tree, output "YES", otherwise output "NO".

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

In the first example, the required tree exists. It has one edge between nodes 1 and 2 with weight 2, another edge between nodes 1 and 3 with weight 7.

In the second example, it is impossible because _d_1, 1 should be 0, but it is 1.

In the third example, it is impossible because _d_1, 2 should equal _d_2, 1.

在第一个例子中，所要求的树存在。它包含一条连接节点 1 和节点 2、权值为 2 的边，以及另一条连接节点 1 和节点 3、权值为 7 的边。

在第二个例子中，这是不可能的，因为 $d_{1,1}$ 应为 0，但其值为 1。

在第三个例子中，这是不可能的，因为 $d_{1,2}$ 应等于 $d_{2,1}$。