ACPC2012Day2OL H.Dungeon(II)

問題

n個の部屋があり、部屋と部屋を結ぶ通路はn-1本存在している。
通路はどちらの方向へも進むことができ、距離が設定されている。
ある部屋からすべての部屋へ行くことが可能である。

危険度とは、ある部屋から別の部屋へ移動するとき、最短で移動するパスの中で部屋間の移動距離が一番長い所の値とする。

部屋の番号がi

考え方

nが大きめで、全探索では間に合わない。
そこで無向グラフとして考え、ある辺に注目し、その辺が何回パスの危険度として採用されるかを考える。

辺の距離がcの所で、その両端が頂点a頂点bとすると、その辺を通るパスで危険度がcになるのは、頂点aまたは頂点bまでで距離がc以下となる辺のみを経由してくるようなパスの数がわかれば、「頂点aまでくる上記のパスの数*頂点bまでにくる上記のパスの数」で求められる。

これを距離が少ない辺から順番に考えていき、その距離が危険度となるパスの数が求められたら、その辺を縮約して、頂点をまとめあげていけばよい。
その距離が危険度となるパスの数というのは、その辺の両端のまとめあげた頂点の数だけが、注目している辺の距離より小さいパスで構成されている数なので、両端の頂点数同士を掛け合わせれば、注目している辺の距離が危険度になるパスの数が求められる。

距離が少ない辺のソートはO(nlogn)で、縮約はUnionFind木でまとめあげた頂点数をO(logn)で求められるようにできるので、全体をO(nlogn)で処理できる。