Link to problem statement (problem D)
For short, in this problem, one is provided the minimal cut matrix T (T(u,v) equals to the minimum cut so that u and v are disconnected), and one needs to find a graph G that satisfies T.
I have solved this problem using the observation: if the solution exists, it must be some sort of spanning trees (it also seems to be the author's solution). However, I have no way to prove my observation. Any hint?
Just in case someone will find this topic later like I did few minutes ago)
I was solving this contest today. Your observation is correct, you may read about Gomory-Hu tree, for every undirected graph one can construct tree with same minimal cut matrix, as Gomory and Hu proved in 1961.