jzoj5883. 【NOIP2018模拟A组9.25】到不了

Description

wy 和 wjk 是好朋友。
今天他们在一起聊天，突然聊到了以前一起唱过的《到不了》。
“说到到不了，我给你讲一个故事吧。”
“嗯？”
“从前，神和凡人相爱了，愤怒的神王把他们关进了一个迷宫里，迷宫是由许多棵有根树组 成的。神王每次把两个人扔进其中的某一棵有根树里面，两个相邻节点的距离为 1，两人的 每一步都只能从儿子走到父亲，不能从父亲走到儿子，他们约定，走到同一个节点相见，由 于在迷宫里面行走十分消耗体力，他们决定找出那个使得他们走的总路程最少的节点，他们 当然会算出那个节点了，可是神王有时候会把两棵有根树合并为一棵，这下就麻烦了。。。”
“唔。。。”
[已经了解树，森林的相关概念的同学请跳过下面一段]
树：由 n 个点，n-1 条边组成的无向连通图。
父亲/儿子：把树的边距离定义为 1,root 是树的根，对于一棵树里面相邻的两个点 u,v，到 root 的距离近的那个点是父亲，到 root 距离远的那个点是儿子
森林：由若干棵树组成的图
[简化版题目描述]
维护一个森林，支持连边操作和查询两点 LCA 操作

Input

第一行一个整数 N，M，代表森林里的节点总数和有根树的数目。
第二行 M 个整数，第 i 个整数 ri 代表第 i 棵有根树的根是编号为 ri 的节点
接下来 N-M 行，每行两个整数 u，v 表示 u 和 v 相邻
接下来一行一个整数 Q，表示 Q 个事件发生了
接下来 Q 行，每行若干个整数，表示一个事件
如果第一个数 op=1，接下来两个整数 u,v,代表神王把 u 号节点所在的树和 v 号节点所在的树 合并到一起(即 u 到 v 连了一条边)，新的根为原来 u 号节点所在的树的根(如果 u,v 已经联通， 忽略这个事件)。
如果第一个数 op=2，接下来两个整数 u，v，代表一次询问，当一个人在 u 号节点，一个人 在 v 号节点，询问他们找到的那个节点的编号

Output

对于每一个询问(op=2 的操作)，输出一行一个整数，代表节点编号，如果 u，v 不联通，输 出 orzorz。

Sample Input

【样例 1】
2 2
1 2
2
1 1 2
2 1 2
【样例 2】
2 2
1 2
2
1 2 1
2 1 2

Sample Output

【样例 1】
1
【样例 2】
2

Data Constraint

对于 30%的数据 1 ≤ N ≤ 1000 1 ≤ Q ≤ 1000
对于 100%的数据 1 ≤ N ≤ 100000 1 ≤ Q ≤ 100000

题解

30%
直接暴力。
100%
其实这道题是很吼（keng）的一道题，因为它其中一个隐藏条件就骗了我好久。
我们发现，每次连完一条边是会把两颗树的形态都改变的。
嘿嘿，于是你想到了什么？
LCT！
似乎这是一种很好的解法。
然而我不会
这对于那些完全没有思绪而会很复杂的数据结构选手是很好的。（无脑数据结构选手）

另外的100%
我们就先不管之前的连边。
我们直接就把
连完边最后的森林的形态弄出来。
然后再进行操作。
每次操作就用并查集来维护当前点的树的根是什么。
分两种情况：
1、连边，如果要连边则把右边的树的并查集连到左边即可。
2、查询。
如果两点并查集不在同一棵树上，则误解。
如果在，那么我们就用a，b，c来分别表示询问的两点以及当前树的根。
然后我们分类讨论这三个点所在不同位置的lca的情况。
(1)

那么$lca(a,c)=lca(b,c)$,然后$Ans=lca(a,b)$
(2)

那么$lca(a,b)=lca(a,c)$,然后$Ans=lca(b,c)$
(3)

那么$lca(a,b)=lca(a,c)$,然后$Ans=lca(b,c)$
(4)

那么$lca(a,b)=lca(c,b)$,然后$Ans=lca(a,c)$
(5)

那么$lca(a,b)=lca(b,c)$,然后$Ans=lca(a,c)$
(6)
那么$lca(a,b)=lca(b,c)$,然后$Ans=lca(a,c)$
其他情况类似。
所以我们可以观察得到：
$Ans=lca(a,b)$ xor $lca(a,c)$ xor $lca(b,c)$

所以就可以在log的时间内解决查询操作啦。

const up=100000;
var
        i,j,k,l,n,m,u,x,y,tot,num,gs,q,my,a,b,c:longint;
        root,nroot:array[1..up] of longint;
        tov,next,last:array[1..2*up] of longint;
        siz,dep,fa,son,top:array[1..up] of longint;
        f,jlf,anf:array[1..up] of longint;
        qu,qx,qy,jx,jy:array[1..up] of longint;
        flag:array[1..up] of boolean;
        a1,b1,c1:longint;

procedure dfsfd(x,f,d:longint);
var
        i,j,k,l:longint;
begin
        fa[x]:=f;
        dep[x]:=d;
        siz[x]:=1;
        flag[x]:=true;
        i:=last[x];
        while i<>0 do
        begin
                if tov[i]<>fa[x] then
                begin
                        dfsfd(tov[i],x,d+1);
                        siz[x]:=siz[x]+siz[tov[i]];
                        if (son[x]=0) or (siz[tov[i]]>siz[son[x]]) then son[x]:=tov[i];
                end;
                i:=next[i];
        end;
end;
procedure dfs(v,num:longint);
var
        i,j,k,l:longint;
begin
        top[v]:=num;
        if son[v]=0 then exit;
        dfs(son[v],num);
        i:=last[v];
        flag[v]:=true;
        while i<>0 do
        begin
                if tov[i]<>fa[v] then
                begin
                        if tov[i]<>son[v] then
                        begin
                                dfs(tov[i],tov[i]);
                        end;
                end;
                i:=next[i];
        end;
end;
procedure insert(x,y:longint);
begin
        inc(tot);
        tov[tot]:=y;
        next[tot]:=last[x];
        last[x]:=tot;
end;
function getfather(x:longint):longint;
begin
        if f[x]<>x then exit(getfather(f[x]));
        exit(f[x]);
end;
function getroot(x:longint):longint;
begin
        if nroot[x]=x then exit(nroot[x]);
        nroot[x]:=getroot(nroot[x]);
        exit(nroot[x]);
end;
procedure get(x,f,d:longint);
var
        i,j,k,l:longint;
begin
        i:=last[x];
        nroot[x]:=d;
        while i<>0 do
        begin
                if tov[i]<>f then
                begin
                        get(tov[i],x,d);
                end;
                i:=next[i];
        end;
end;
function getlca(x,y:longint):longint;
var
        i,j,tx,ty,k:longint;
begin
        tx:=top[x];
        ty:=top[y];
        k:=maxlongint;
        while tx<>ty do
        begin
                if dep[tx]<dep[ty] then
                begin
                        y:=fa[ty];
                        ty:=top[y];
                end
                else
                begin
                        x:=fa[tx];
                        tx:=top[x];
                end;
        end;
        if dep[x]>dep[y] then
        begin
                exit(y);
        end
        else
        begin
                exit(x);
        end;
end;
begin
        assign(input,'arrival.in');reset(input);
        assign(output,'arrival.out');rewrite(output);
        readln(n,m);
        for i:=1 to n do
        begin
                f[i]:=i;
                nroot[i]:=i;
        end;
        for i:=1 to m do
        begin
                read(root[i]);
        end;
        for i:=1 to n-m do
        begin
                readln(x,y);
                insert(x,y);
                insert(y,x);
        end;
        for i:=1 to m do
        begin
                get(root[i],0,root[i]);
        end;
        jlf:=nroot;
        readln(q);
        for i:=1 to q do
        begin
                readln(qu[i],qx[i],qy[i]);
                x:=getroot(qx[i]);
                y:=getroot(qy[i]);
                jx[i]:=x;
                jy[i]:=y;
                if qu[i]=1 then
                begin
                        if x<>y then
                        begin
                                insert(qx[i],qy[i]);
                                insert(qy[i],qx[i]);
                                nroot[y]:=x;
                        end;
                end;
        end;
        for i:=1 to m do
        begin
                j:=getroot(root[i]);
                if not flag[j] then
                begin
                        dfsfd(j,0,1);
                        dfs(j,j);
                end;
        end;
        nroot:=jlf;
        for i:=1 to q do
        begin
                if qu[i]=1 then
                begin
                        nroot[jy[i]]:=jx[i];
                end
                else
                begin
                        c:=jy[i];
                        if c<>jx[i] then
                        begin
                                writeln('orzorz');
                        end
                        else
                        begin
                                a:=qy[i];
                                b:=qx[i];
                                a1:=getlca(a,b);
                                b1:=getlca(a,c);
                                c1:=getlca(b,c);
                                writeln(a1 xor b1 xor c1);
                        end;
                end;
        end;
end.