大神进来看看

#include <iostream>
#include <cstdio>
using std::cin;
using std::cout;
using std::endl;
int n,m;
bool deleted[100002];
struct nd
{
	int lson, rson, val;
	short depth;
	nd()
	{
		lson=rson=val=depth=0;
	}
} node[100002];
void swap(int& a, int& b)
{
	a=a^b;
	b=a^b;
	a=a^b;
	return;
}
#define cmp(i, j) (node[i].val==node[j].val?i<j:node[i].val<node[j].val)
int fa[100002];
int find_anc(int i)
{
	while (fa[i]!=i)
		i=fa[i];
	return i;
}
int merge(int i, int j)
{
	if (i==0||j==0)
		return i+j;
	i=find_anc(i);
	j=find_anc(j);
	if (i==j)
		return 0;
	if (!cmp(i, j))
		swap(i, j);
	node[i].rson=merge(node[i].rson, j);
	fa[node[i].rson]=i;
	int& ls=node[i].lson;
	int& rs=node[i].rson;
	if (node[ls].depth<=node[rs].depth)
		swap(ls, rs);
	node[i].depth=node[node[i].rson].depth+1;
	return i;
}
int query(int x)
{
	return deleted[x]?-1:node[find_anc(x)].val;
}
void del(int x)
{
	x=find_anc(x);
	if (deleted[x])
		return;
	deleted[x]=true;
	if (node[x].lson)
		fa[node[x].lson]=node[x].lson;
	if (node[x].rson)
		fa[node[x].rson]=node[x].rson;
	merge(node[x].lson, node[x].rson);
	return;
}
int main()
{
	node[0].depth=-1;
	cin>>n>>m;
	for (int i=1; i<=n; ++i)
		cin>>node[i].val;
	for (int i=1; i<=n; ++i)
		fa[i]=i;
	for (int i=1; i<=m; ++i)
	{
		int cmd, x, y;
		cin>>cmd;
		if (cmd==1)
		{
			cin>>x>>y;
			if (deleted[x]||deleted[y])
				continue;
			merge(x, y);
		}
		else if (cmd==2)
		{
			cin>>x;
			cout<<query(x)<<endl;
			del(x);
		}
	}
	return 0;
}