简要题意

维护一颗动态的内向树，支持求 LCA 以及 link / cut 操作。

Sol

和 模板 的区别是多了一个求 LCA，这个可以两个点分别 access，取后者最后一次经过的点即为两点的 LCA。

由于本题的边很特殊，每次只会接上 / 摘下一整颗子树，所以 LCT 的 link / cut 都可以大大简化，makeroot 也不用，还不用维护路径信息，其实比模板短多了。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e6 + 5;
struct LCT
{
	struct node {int ch[2], fath;} tr[maxn];
	#define l(k) tr[k].ch[0]
	#define r(k) tr[k].ch[1]
	#define f(k) tr[k].fath
	int get(int k) {return k == r(f(k));}
	bool isroot(int k) {return tr[f(k)].ch[get(k)] != k;}
	void rotate(int k)
	{
		int p = f(k), pp = f(p), t = get(k);
		f(k) = pp;
		if(!isroot(p)) tr[pp].ch[get(p)] = k;
		f(tr[p].ch[t] = tr[k].ch[t ^ 1]) = p;
		f(tr[k].ch[t ^ 1] = p) = k;
	}
	void splay(int k)
	{
		while(!isroot(k))
		{
			int p = f(k);
			if(!isroot(p)) rotate(get(k) == get(p)? p: k);
			rotate(k);
		}
	}
	int access(int x)
	{
		int pre = 0;
		for(; x; pre = x, x = f(x)) splay(x), r(x) = pre;
		return pre;
	}
	int find(int x)
	{
		access(x), splay(x);
		while(l(x)) x = l(x);
		return splay(x), x;
	}
	void link(int x, int y) {access(x), splay(x), f(x) = y;}// x->y
	void cut(int x, int y) {access(x), splay(y), r(y) = f(x) = 0;}// x-/->y
	#undef l
	#undef r
	#undef f
	#undef t
}tree;
int n, m, f[maxn];
int main()
{
    scanf("%d%d", &n, &m);
	for(int i = 1, op, a, b; i <= m; i++)
	{
        scanf("%d%d", &op, &a);
        if(op == 1) scanf("%d", &b), tree.link(a, f[a] = b);
        if(op == 2) tree.cut(a, f[a]);
        if(op == 3)
        {
            scanf("%d", &b);
            if(tree.find(a) != tree.find(b)) puts("-1");
            else tree.access(a), printf("%d\n", tree.access(b));
        }
	}
	return 0;
}

::::