← 返回题目列表

AtCoder · abc451_e

H. 树距离

中文机器翻译题面 查看原题

分数: 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