分数: 475 点
问题陈述
判断是否存在带权无向树 N 满足以下条件的顶点。
- 对于任意两个整数 i 和 j 与 1 \le i \lt j \le N,顶点之间的距离 i 和 j is A_{i,j}.
这里,顶点之间的距离 i 和 j 被定义为连接这两个顶点的唯一简单路径上的边的权重之和。
约束
- 2 \le N \le 3000
- 1 \le A_{i,j} \le 9999
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_{1, 2} A_{1, 3} \ldots A_{1, N}
A_{2, 3} \ldots A_{2, N}
\vdots
A_{N-1,N}
输出
如果存在满足条件的树,则输出 Yes;否则,输出 No.
示例输入 1
4 2 5 4 3 2 5
示例输出 1
Yes
例如,具有以下边的树满足条件。
- 边缘 (1, 2) 有重量 2.
- 边缘 (2, 3) 有重量 3.
- 边缘 (2, 4) 有重量 2.
因此,输出 Yes.
示例输入 2
4 2 5 4 3 2 6
示例输出 2
No
不存在满足条件的树。因此,输出 No.
示例输入 3
10 1039 1802 3781 231 5828 1944 392 262 1481 763 2742 1270 4789 905 1431 1301 442 1979 2033 5552 142 2194 2064 1205 4012 7531 2121 4173 4043 3184 6059 2175 161 493 1712 5694 6220 6090 5231 2336 2206 1347 654 1873 1743
示例输出 3
Yes