测试点12T掉了 1.20s

#include<bits/stdc++.h>
using namespace std;
int ls,rs,tx,ty,x,y,flag,n,m,f[114514],key[114514],dist[114514],l[114514],r[114514],parent[114514];
bool bijiao(int A,int B)
{
    if(key[A]==key[B]) 
        return A<B;
    else
        return key[A]<key[B];
}
int ff(int x)
{
//  if(parent[x]<0)
//      return x;
//  else
//      return ff(parent[x]);
    return parent[x]<0?x:ff(parent[x]);
}
int merge(int A,int B) 
{
    if(!A or !B)return A+B;
//    if(key[B]<key[A])
    if(!bijiao(A,B)) 
        swap(A,B);
    r[A]=merge(r[A],B);
    parent[r[A]]=A;
    if(dist[l[A]]<dist[r[A]])
        swap(l[A],r[A]);
    dist[A]=dist[r[A]]+1;
    return A;
}
void Delete(int x)
{
    ls=l[x];
    rs=r[x];
    key[x]=parent[ls]=parent[rs]=-1;
    merge(ls,rs);
}
int main()
{
//  freopen("P3377_11.in","r",stdin);
//  freopen("P3377_111.out","w",stdout);
    scanf("%d%d",&n,&m);
    dist[0]=-1;
    memset(parent,-1,sizeof(parent));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&key[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&flag);
        if(flag==1)
        {
            scanf("%d%d",&x,&y);
            if(key[x]<0 or key[y]<0)
                continue;
            tx=ff(x),ty=ff(y);
            if(tx==ty)
                continue;
            merge(tx,ty);
        }
        if(flag==2)
        {
            scanf("%d",&x);
            if(key[x]==-1)
            {
                puts("-1");
                continue;
            }
            tx=ff(x);
            printf("%d\n",key[tx]);
            Delete(tx);
        }
    }
}