ABC 451 E — Tree Distance

考察

根を頂点1に固定する。正辺重みの木でiの真の祖先jならA_{1,j}+A_{j,i}=A_{1,i}である。逆にこの等式を満たす頂点はrootからiへのpath上にあり、i自身も等式を満たすので候補から必ず除外する。残る真祖先のうちA_{j,i}が最小の頂点が親である。

各i≠1についてその親と重みA_{j,i}の辺を内部で構成し、全頂点対の木距離をAと照合する。全て一致すればYes、一つでも違えばNo。出力はYes/Noのみなので、構成した辺は判定の検証に使い外へ出さない。

典型の発動条件

距離行列からの木復元

発動条件: 正重み木の全点対距離が与えられ、存在判定と構成を行うとき。

root 距離の加法等式から祖先・親を特定する。

候補構成後の完全検証

発動条件: 局所条件で唯一候補を作れるが十分性の直接判定が複雑なとき。

候補 object の定義量を再計算して入力と全一致させる。

問題固有の要素

存在するなら一意に決まる構造では、必要条件で候補を強制構成し、最後に直接検証する方が判定条件を簡潔にできる。

別の問題へ持ち帰る視点: 木距離の equality は path 上包含を表し、root を選ぶことで親子関係へ順序化できる。

正当性

有効な正辺木ではrootからiへのpath上の真祖先だけが距離加法等式を満たし、iを除いた最も近い祖先は直前の親である。よって存在する木なら手順はその親辺を復元する。逆に構成候補の全点対距離が入力と一致すれば、その候補木自体が入力を実現するため、Yes判定も十分である。

実装上の注意

  • 親候補はj≠iに制限し、A_{j,i}が最小の真祖先を選ぶ。候補木の距離を全点対で検証する。
  • 問題の出力はYes/Noだけであり、復元辺を出力しない。

復習の核

  • 祖先等式の必要十分性と「最も近い祖先=親」を tree path で証明し、構成後検証が反例を全て排除する理由を確認する。

計算量と制約

時間

距離行列N²。各点親候補O(N²)、全始点木DFS O(N²)。

空間

入力距離O(N²)、候補木O(N)。

制約との対応

公式制約の確認範囲: Time limit: 6 sec; Memory limit: 1024 MiB; Constraints: 2 \le N \le 3000; 1 \le A_{i,j} \le 9999; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Tree Distance の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 加法的tree metric復元

主題
  • 加法的tree metric復元: 加法的距離行列から正重み木の候補を復元し、全点対距離の再計算で存在を完全検証できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 加法的tree metric復元

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 加法的tree metric復元

      • 加法的距離行列から正重み木の候補を復元し、全点対距離の再計算で存在を完全検証できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題