icontofig | 发布于 2019-08-03 20:58:54 | 阅读量 257 | 左偏树 并查集

## 代码

```#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
int f[maxn];
int hp[maxn],d[maxn],val[maxn],l[maxn],r[maxn];
int find(int x){
if(f[x] != x) f[x] = find(f[x]);
return f[x];
}
int n,m,a,b;
int merge(int a,int b){
if(!a || !b)return a + b;
if(val[a] < val[b]){
swap(a,b);
}
r[a] = merge(r[a],b);
f[r[a]] = a;
if(d[r[a]] > d[l[a]])swap(l[a],r[a]);
d[a] = d[r[a]] + 1;
return a;
}
void solve(int x,int y){
int p = find(x),q = find(y);
if(p == q){
printf("-1\n");
return;
}
int t = merge(p,q);
printf("%d\n",val[t] / 2);
val[t] /= 2;
f[l[t]] = l[t];
f[r[t]] = r[t];
int p1 = l[t],p2 = r[t];
l[t] = 0;
r[t] = 0;
d[t] = 0;
int k = merge(p1,p2);
t = merge(t,k);
return;
}
int main(){
while(scanf("%d",&n) != EOF){
for(int i = 1;i <= n;++i)
val[i] = get_num();
for(int i = 1;i <= n;++i){
f[i] = i;
l[i] = r[i] = d[i] = 0;
}
m = get_num();
while(m--){
a = get_num();
b = get_num();
solve(a,b);
}
}
return 0;
}```

257 人读过

0 条评论