나무 행렬

시간 제한2초메모리 제한2048 MB

요약

대칭이고 대각선이 0인 n x n 거리 행렬이 양의 간선 길이를 가진 트리의 정점 간 거리와 일치하는지 판별합니다.

난이도: 보통10점 중 7점
유형: 트리, 구현, 수학
정답자: 아직 제출이 없습니다

문제

음이 아닌 정수로 이루어진 크기 $n \times n$ 정사각 행렬이 주어진다. 이 행렬은 주대각선에 대해 대칭이고, 주대각선의 원소는 모두 0이다. 정점이 $n$ 개인 무방향 트리 $T$ 가 있고, 간선의 길이가 모두 양수이며, 각 칸 $(i, j)$ 에 정점 $i$ 와 $j$ 사이의 $T$ 상 거리가 들어 있으면 이 행렬을 나무 행렬이라고 한다.

주어진 행렬이 나무 행렬인지 판단하라.

입력

첫 줄에 정수 $n$ 이 주어진다 ( $1 \le n \le 1000$ ). 이어서 $n$ 개의 줄에 행렬의 원소인 정수 $n$ 개씩, 즉 $d_{i,j}$ ( $0 \le d_{i,j} \le 10^9$ )가 주어진다. 행렬은 주대각선에 대해 대칭이다. 주대각선의 원소는 0이고, 나머지 원소는 모두 양의 정수이다.

출력

행렬이 나무 행렬이면 "Yes", 아니면 "No"를 출력한다. 대소문자는 구분하지 않는다.

예제2

예제 1
입력
```
3
0 1 3
1 0 2
3 2 0
```
예상 출력
```
Yes
```
예제 2
입력
```
3
0 1 3
1 0 1
3 1 0
```
예상 출력
```
No
```