欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - ZOJ2334
题目传送门 - HDU1512
题意概括
在一个森林里住着N(N<=10000)只猴子。在一开始，他们是互不认识的。但是随着时间的推移，猴子们少不了争斗，但那只会发生在互不认识(认识具有传递性)的两只猴子之间。争斗时，两只猴子都会请出他认识的猴子里最强壮的一只(有可能是他自己)进行争斗。争斗后，这两只猴子就互相认识。每个猴子有一个强壮值，但是被请出来的那两只猴子进行争斗后，他们的强壮值都会减半(例如10会减为5，5会减为2)。现给出每个猴子的初始强壮值，给出M次争斗，如果争斗的两只猴子不认识，那么输出争斗后两只猴子的认识的猴子里最强壮的猴子的强壮值，否则输出 -1。
题解
左偏树大力维护。
找根就最暴力的来。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=100005;
int n,m;
int fa[N],ls[N],rs[N],npl[N],val[N];
int getf(int k){
while (fa[k])
k=fa[k];
return k;
}
int merge(int a,int b){
if (!a||!b)
return a+b;
if (val[a]<val[b])
swap(a,b);
rs[a]=merge(rs[a],b);
fa[rs[a]]=a;
if (npl[rs[a]]>npl[ls[a]])
swap(rs[a],ls[a]);
npl[a]=npl[rs[a]]+1;
return a;
}
int weaken(int a){
fa[ls[a]]=fa[rs[a]]=0;
int b=merge(ls[a],rs[a]);
fa[a]=ls[a]=rs[a]=npl[a]=0;
val[a]>>=1;
return merge(a,b);
}
int main(){
while (~scanf("%d",&n)){
for (int i=1;i<=n;i++){
scanf("%d",&val[i]);
fa[i]=ls[i]=rs[i]=npl[i]=0;
}
scanf("%d",&m);
while (m--){
int a,b;
scanf("%d%d",&a,&b);
a=getf(a),b=getf(b);
if (a==b){
puts("-1");
continue;
}
a=weaken(a);
b=weaken(b);
printf("%d\n",max(val[a],val[b]));
merge(a,b);
}
}
return 0;
}