eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сумма на дереве наоборот

Сумма на дереве наоборот

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

В задаче 2157 Сумма для заданного дерева следует найти суммарную длину всех путей в дереве.

Сейчас мы предлагаем Вам решить обратную задачу. Задана матрица расстояний между всеми вершинами дерева с n вершинами. Необходимо определить, может ли эта матрица быть матрицей попарных расстояний между всеми вершинами взвешенного дерева. Все веса ребер дерева должны быть натуральными числами.

Giriş verilənləri

Первая строка содержит размер матрицы n (1n1000). Далее следует матрица расстояний: в n строках расположены n целых неотрицательных чисел, не превосходящих 10^9 - расстояния между парами вершин.

Çıxış verilənləri

Вывести YES, если такое дерево существует, и NO иначе.

Nümunə

Giriş verilənləri #1
3
0 5 1
5 0 6
1 6 0
Çıxış verilənləri #1
YES