Помимо прочего, можно придумывать новые задачи, решая обратные задачи к старым задачам. Обратная задача — это когда в качестве входных данных даются выходные данные исходной задачи и нужно сгенерировать в качестве выходных данных такие входное данные, что решение исходной задачи на них выдавало бы заданные входные данные. Самая сложная задача Topcoder Open 2014 раунда 2C, InverseRMQ, является хорошим примером такого подхода.
Попробуем придумать новую задачу таким способом. В качестве основы используем следующую задачу: задано дерево; подсчитайте расстояние между всеми парами его вершин. Да, это просто. Но обратная версия этой задачи куда сложнее: задана матрица расстояний размера n × n. Определите, может ли данная матрица быть матрицей всех попарных расстояний между вершинами взвешенного дерева (все веса должны быть целыми положительными числами).
Выходные данные
Если такое дерево существует, выведите «YES», в противном случае выведите «NO».
Примечание
В первом примере необходимое дерево существует. Оно состоит из ребра между вершинами 1 и 2 с весом 2 и ребра между вершинами 1 и 3 с весом 7.
Во втором примере дерево не существует, потому что d1, 1 должно равняться 0, а оно равняется 1.
В третьем примере дерево не существует, потому что d1, 2 должно равняться d2, 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 7
2 0 9
7 9 0
|
YES
|
|
2
|
3
1 2 7
2 0 9
7 9 0
|
NO
|
|
3
|
3
0 2 2
7 0 9
7 9 0
|
NO
|
|
4
|
3
0 1 1
1 0 1
1 1 0
|
NO
|
|
5
|
2
0 0
0 0
|
NO
|