左偏树。我是ziliuziliu，我是最强的
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 100500 using namespace std; int root[maxn],ls[maxn],rs[maxn],val[maxn],father[maxn],n,m; int x,y,dis[maxn]; int find(int x) { if (x!=father[x]) father[x]=find(father[x]); return father[x]; } int merge(int x,int y) { if (x==0) return y; else if (y==0) return x; if (val[x]<val[y]) swap(x,y); rs[x]=merge(rs[x],y); father[rs[x]]=x; if (dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]); if (rs[x]==0) dis[x]=0; else dis[x]=dis[rs[x]]+1; return x; } int pop(int x) { father[x]=x; father[ls[x]]=ls[x]; father[rs[x]]=rs[x]; int regis=merge(ls[x],rs[x]); ls[x]=rs[x]=dis[x]=0; return regis; } int main() { while (scanf("%d",&n)!=EOF) { memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); dis[0]=-1; for (int i=1;i<=n;i++) { scanf("%d",&val[i]); father[i]=i; root[i]=i; } scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); int pa,pb; pa=find(x),pb=find(y); if (pa==pb) printf("-1 "); else { val[pa]/=2;val[pb]/=2; int nn1,nn2; nn1=pop(pa);nn2=pop(pb); nn1=merge(nn1,pa); nn1=merge(nn1,pb); nn1=merge(nn1,nn2); printf("%d ",val[find(pa)]); } } } return 0; }