以下 \(A_{i,j} = A_{j,i}\) として \(i > j\) についても距離を定義します。また、制約より辺の重みはすべて正整数であることに注意してください。

条件を満たす木 \(T\) を具体的に構築することを考えます。このとき、木の満たすべき性質から \(T\) が存在するのであればただ \(1\) 通りに定まり、以下の手順で構築できます。

頂点 \(1\) を根として、頂点 \(i \ (i \ne 1)\) の親 \(p_i\) と、親との間の辺の重み \(w_{i, p_i}\) を特定することを考えます。

頂点 \(i\) について、ある頂点 \(j\) が \(i\) の祖先となるための必要十分条件は \(A_{1,j} + A_{j,i} = A_{1,i}\) を満たすことです。この条件を満たす頂点 \(j \ (j \ne i)\) の集合を \(S_i\) とします。

この集合 \(S_i\) に含まれる頂点のうち、\(i\) の親となることができるのは \(\displaystyle p_i = \argmin_{j \in S_i} A_{i, j}\) を満たす頂点です。また、その辺の重みは \(w_{i, p_i} = A_{i,p_i}\) となります。

もし \(S_i\) が空の場合、これは親が存在せず \(T\) が構築できないため、答えは No となります。また \(p_i\) の候補が複数存在する場合も No となります。（実装上は適当な tie-break をいれておけば、判定時に矛盾が検出されます）

以上の手順により、木 \(T\) の候補が \(O(N^2)\) で構築できます。

最後に、構築した木が実際に条件を満たすかを確認します。各頂点を始点として DFS などを行い、全頂点間の距離が入力の \(A\) と完全に一致するかを判定すればよいです。全体の計算量は \(O(N^2)\) となります。