10 pts。

其中第一个点就 MLE。

思路是将权值的相反数加入左偏树中。

对于每次询问的 $x,y$，找出其根节点 $a,b$，并新建权值分别为 $a,b$ 的一半的点与它们合并，再删去 $a,b$ 这两个点，最后合并这两颗树。

下载了第一个数据点，答案是对的，跑的也挺正常。

按理说，加上新建的点应该会有 300000 个，但是不管开大开小第一个点都是 MLE。

求助原因。

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 10010//目前这个不用管它，[10000 - 2000000]都是 MLE
#define INF 0x3f3f3f3f
//#define int long long

using namespace std;

int n,m,cnt;

int read(){
  int s=0,w=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
  return s*w;
}

namespace LIT{
  #define ls lson[x]
  #define rs rson[x]
  bool vis[maxn];
  int fa[maxn],dis[maxn];
  int lson[maxn],rson[maxn];
  
  struct node{
    int pos,val;
    bool operator < (const node &b) const{
      return val^b.val?val<b.val:pos<b.pos;  
    } 
  }v[maxn];
  
  int findf(int x){
    return fa[x]==x?x:fa[x]=findf(fa[x]);
  }
  
  int merge(int x,int y){
    if(!x||!y) return x+y;
    if(v[y]<v[x]) swap(x,y);
    rs=merge(rs,y);
    if(dis[ls]<dis[rs])swap(ls,rs);
    dis[x]=dis[rs]+1;
    return x;
  }
}

using namespace LIT;

signed main(){
  n=read();dis[0]=-1;
  for(int i=1;i<=n;i++){
    v[i].val=read()*-1;
    v[i].pos=fa[i]=i;
  }
  m=read();cnt=n;
  for(int i=1,x,y;i<=m;i++){
    x=findf(read());y=findf(read());
    if(x==y){printf("-1\n");continue;}
    
    v[++cnt].pos=fa[cnt]=cnt;v[cnt].val=-(-v[x].val>>1);//新建第一个
    fa[cnt]=fa[x]=merge(cnt,x);//合并第一个
    fa[lson[x]]=fa[rson[x]]=fa[x]=merge(lson[x],rson[x]);//删去原根节点
    lson[x]=rson[x]=dis[x]=0;
    
    v[++cnt].pos=fa[cnt]=cnt;v[cnt].val=-(-v[y].val>>1);//第二个同上
    fa[cnt]=fa[y]=merge(cnt,y);
    fa[lson[y]]=fa[rson[y]]=fa[y]=merge(lson[y],rson[y]);
    lson[y]=rson[y]=dis[y]=0;
    
    int fir=findf(cnt-1),sec=findf(cnt);
    fa[fir]=fa[sec]=merge(fir,sec);//合并两棵树
    printf("%d\n",-v[findf(fir)].val);
  }
  return 0;
}

附第一个点数据：

16
8034
1215
24625
30817
5188
18504
10811
32596
13932
15464
4297
19261
10610
6349
8766
5223
37
14 1
13 8
12 15
6 7
4 2
7 7
1 12
3 1
8 1
4 5
12 5
3 10
16 5
10 10
4 6
6 14
3 4
14 8
2 1
1 8
8 16
8 2
13 3
14 11
8 1
13 12
12 12
16 14
6 8
7 4
9 10
1 16
13 2
10 2
5 5
6 7
5 4

4017
16298
9630
9252
15408
-1
4815
12312
8149
7704
6156
7732
5305
-1
5405
-1
-1
-1
-1
-1
-1
-1
-1
4626
-1
-1
-1
-1
-1
-1
6966
-1
-1
-1
-1
-1
-1