题目描述

有一种简单的方法可以从一个旧题目中获得一个新题目，叫做“反向题目”：我们给出原题的输出，然后要求构造一个输入，使得原题的解法能够产生我们给定的输出。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"。

输入输出样例 #1

输入 #1

3
0 2 7
2 0 9
7 9 0

输出 #1

YES

输入输出样例 #2

输入 #2

3
1 2 7
2 0 9
7 9 0

输出 #2

NO

输入输出样例 #3

输入 #3

3
0 2 2
7 0 9
7 9 0

输出 #3

NO

输入输出样例 #4

输入 #4

3
0 1 1
1 0 1
1 1 0

输出 #4

NO

输入输出样例 #5

输入 #5

2
0 0
0 0

输出 #5

NO

说明/提示

有一种简单的方法可以从一个旧题目中获得一个新题目，叫做“反向题目”：我们给出原题的输出，然后要求构造一个输入，使得原题的解法能够产生我们给定的输出。Topcoder Open 2014 Round 2C 的难题 InverseRMQ 就是一个很好的例子。

现在让我们用这种方式创造一个新题目。我们将使用这样一道题目：给定一棵树，请计算任意两点间的距离。没错，这很简单，但它的反向版本要难一些：你现在给定一个 $n \times n$ 的距离矩阵，判断它是否是某棵加权树（所有权值都必须为正整数）的距离矩阵。

由 ChatGPT 5 翻译