Cosmic Station (UVa Live Archive Europe - Southeastern - 2010/2011 Bucharest (Romania))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4822

問題

木がある。葉同士の距離を与えるので葉以外の頂点が何個あるか求めよ。
3<=葉の数<=1024
答え<1024

解法

大前提として葉同士の距離が決まっていると木自体が決定できる。なので、実際に木を復元して頂点数を求めることにする。
葉を順番にl1,l2,...,lnとする。まずl1,l2の間にある頂点の数はすぐに求まる。lk-1までの葉の関係によりそこまでの木が復元されている時に、新しくlkの葉を追加することを考える。葉の距離の関係上、(l1,l2)のパス上で(l1,lk)、(l2,lk)へのパスが同時に存在する頂点はただ一つしか無いので次は(l1,l3)、(l1,l4)…と続けていけば、(l1,lk)へのパスが求まる。これをdfsで上手く実装するとO(n^2)で木が復元できる。