2013年JOI春合宿4日目宇宙船（SpaceShips）

問題文が「これ木構造だから！木構造だからね！そこんとこよろしく！」と語りかけてくる問題．

概要

N個の星があって，それぞれの星は1つの宇宙船を保有している．

ある星aが保有している宇宙船を別の星bに向かわせるとき人を乗せていくことができるが，帰りは乗せていけない．（宇宙船は何回でも往復する）

この問題に対してQ個のクエリが与えられる．クエリの種類は以下の通り．

宇宙船を使っていない星aから星bへのルートで星aの宇宙船を使う．（ただし，星bから星aへはどのようなルートを使っても到達できない）
星aの宇宙船を使っていない状態にする．
星aと星bからそれぞれ出発して合流できる星cを見つける．そのような星cが複数あるならば，合流するまでの距離が最も短いものを見つける．

NとQの上限は1000000である．

解法

問題文から明らかに根付き木のLCA(Lowest Common Ancestor)に帰着する．

ただのLCAならダブリングとかを用いてそれなりの実装量で解けるが，今回は経路の変更とかがあるので使えない．

そこでLinkCut木を使う．
クエリの1番目と2番目はLinkCut木のLink操作とCut操作に対応する．

3番目のクエリについては，a，bからそれぞれfindrootを行ってその結果が等しくなければaとbは同じ木に属していないことがわかる．
同じ木に属していることが分かった場合は，LinkCut木の動作に焦点を当てて考える．
まず，aでfindrootをすると，aについてexpose操作が行われる．次にbでfindrootすると，bについてexposeが行われる．この時，aが所属するパスはbと共通の道をたどり始めたところで切れてしまう．
すなわち，aが所属するパスの接続先を求めてその値を出力すればいい．

ただし，aがbの祖先である場合はその限りでない．そのような場合にbでexposeすると，bの含まれるパスの中にaが所属してしまう．この時，aの所属するパスの接続先はnullになるのでそのような場合には，aを答えとして出力する．

実装量は(もちろんLinkCut木を除けばの話だが）そんなに重くない．
findtailはパスの中で根に最も近い頂点を探す操作だが，「こんなこと書かなくても普通にaの親が接続先さしてるじゃん！」とさっき気が付いた．

それにしても，こんなに実装が重いデータ構造を必要とする問題が出るとか．．．やっぱりIOIerはおかしい．

/* LinkCut木のソースは別の記事を参照 */
int N, Q;
int main(){
    scanf("%d%d", &N, &Q);
    LinkCutTree tree(N);
    for(int t = 0; t < Q; ++t){
        int T, A, B;
        scanf("%d", &T);
        if(T == 1){
            scanf("%d%d", &A, &B);
            tree.link(A-1, B-1);
        }
        else if(T == 2){
            scanf("%d", &A);
            tree.cut(A-1);
        }
        else if(T == 3){
            int a, b, c;
            scanf("%d%d", &A, &B);
            a = tree.findroot(A-1);
            b = tree.findroot(B-1);
            if(a == b){
                if((c = tree.findtail(A-1)) == a){
                    c = A;
                }
                else{
                    c = tree.nodes[c].pp -> id + 1;
                }
            }
            else{
                c = -1;
            }
            printf("%d\n", c);
        }
    }
    return 0;
}