JOI春合宿day4 : Spaceships

木 データ構造

問題文↓

http://imoz.jp/data/joi/2013-sp-d4-spaceships.pdf

ジャッジ↓

3: 宇宙船 (Spaceships) - 2013年 日本情報オリンピック春合宿 4日目 | AtCoder

問題概要

  • N個の頂点とQ個のクエリがきます。
  • 頂点を結ぶ辺の関係は森か木であることが保証されています。
  • クエリは次の三種類です。
  1. 頂点a の親を頂点b とする。
  2. 頂点a とその親を結ぶ辺を削除する
  3. 頂点a と 頂点b のLCAを出力する。

解法

  • Link-cut tree
  • いろんな場所を参考にして頑張って作る。（参考ＵＲＬは下記）
  • Ｌｉｎｋ-cut tree 上でＬＣＡを求める。
    ＬＣＡはexpose()をフル活用しながら親をたどっていく。
  • スプレー木で実装されているので木の高さはＬｏｇＮ程度になる。
    （計算量の細かい解析は難しい）
  • コードに頑張って解読するためのコメントアウトの嵐があります。
ソースコード

感想

Link-Cut Tree やべえええええ

作問につかいたい。

参考：以下をがん見しました。

www.slideshare.net

www.slideshare.net