AT_abc451_e.[ABC451E] Tree Distance

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

$ N $ 頂点の重み付き無向木であって、以下の条件を満たすものが存在するか判定して下さい。

$ 1 \le i \lt j \le N $ を満たす任意の $ 2 $ 整数 $ i,j $ について頂点 $ i $ と頂点 $ j $ の距離が $ A_{i,j} $ である。

ただし、頂点 $ i $ と頂点 $ j $ の距離とは、この $ 2 $ 頂点を結ぶ唯一の単純パスに含まれる辺の重みの総和のことです。

输入格式

入力は以下の形式で標準入力から与えられる。

$ 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
```
输入#2
```
4
2 5 4
3 2
6
```
输出#2
```
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

说明/提示

Sample Explanation 1

例えば以下の辺をもつ木が条件を満たします。

辺 $ (1, 2) $ の重みが $ 2 $
辺 $ (2, 3) $ の重みが $ 3 $
辺 $ (2, 4) $ の重みが $ 2 $

よって Yes と出力してください。

Sample Explanation 2

条件を満たす木は存在しません。よって No と出力してください。

Constraints

$ 2 \le N \le 3000 $
$ 1 \le A_{i,j} \le 9999 $
入力される値は全て整数

输入解题思路，AI测评打分。不知道怎么写?

首页