Məsələlər
Сумма на дереве наоборот
Сумма на дереве наоборот
В задаче 2157 Сумма для заданного дерева следует найти суммарную длину всех путей в дереве.
Сейчас мы предлагаем Вам решить обратную задачу. Задана матрица расстояний между всеми вершинами дерева с n вершинами. Необходимо определить, может ли эта матрица быть матрицей попарных расстояний между всеми вершинами взвешенного дерева. Все веса ребер дерева должны быть натуральными числами.
Giriş verilənləri
Первая строка содержит размер матрицы n (1 ≤ n ≤ 1000). Далее следует матрица расстояний: в 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