読者です 読者をやめる 読者になる 読者になる

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
  • いろんな場所を参考にして頑張って作る。(参考URLは下記)
  • Link-cut tree 上でLCAを求める。
    LCAはexpose()をフル活用しながら親をたどっていく。
  • スプレー木で実装されているので木の高さはLogN程度になる。
    (計算量の細かい解析は難しい)
  • コードに頑張って解読するためのコメントアウトの嵐があります。
ソースコード

感想

Link-Cut Tree やべえええええ

作問につかいたい。

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

www.slideshare.net

www.slideshare.net