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 (1 ≤ n ≤ 1000). 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.
3 0 5 1 5 0 6 1 6 0