favorite We need a little bit of your help to keep things running, click on this banner to learn more

Shortest paths - interesting graph problems

Sum on a tree reversed

The problem 2157 Sumмfor a given weighted tree asks to find the total length of all paths in the tree.

Now we propose you to solve the inverse problem. Given a distance matrix between all the nodes of a tree with n vertices. Determine whether this matrix is a matrix of pairwise distances between all vertices of weighted tree. All the weights of the tree edges should be positive integers.


The first line contains the size of the matrix n (1n1000). Then given the matrix itself: n lines contain n nonnegative integers, not exceeding 109 - the distances between the pairs of vertices.


Print YES, if such tree exists, and NO otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 5 1
5 0 6
1 6 0
Output example #1