再来存板子呀（再写一遍忽然发现我对指针的概念感受产生了危机）

Problem

板子（有个根权值 / 2 的操作，删了再合并就行）

Solution

记得清指针 qwq

Code

// Code by ajcxsu
// Problem: left-pian-tree

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int n, m;
const int N=1e5+10;
struct Node *nil;
struct Node {
    Node *ls, *rs, *f;
    int v, dis;
} *rt[N], po[N];
int a[N];
void ini() {
    nil=po, nil->ls=nil->rs=nil->f=nil, nil->v=nil->dis=0;
    for(int i=1;i<=n;i++) rt[i]=po+i, *rt[i]=*nil, rt[i]->v=a[i];
}
Node *Find(Node *x) { return x->f!=nil?x->f=Find(x->f):x; }
Node *Merge(Node *a, Node *b) {
    if(a==nil) return b;
    if(b==nil) return a;
    if(a->v<b->v) swap(a, b);
    a->rs=Merge(a->rs, b), a->rs->f=a;
    if(a->ls->dis<a->rs->dis) swap(a->ls, a->rs);
    a->dis=a->rs->dis+1;
    return a;
}
Node *Reduce(Node *a) {
    Node *l=a->ls, *r=a->rs;
    a->ls=a->rs=l->f=r->f=nil, a->v>>=1, a->dis=0; // important
    return Merge(Merge(l, r), a);
}

int main() {
    ios::sync_with_stdio(false);
    while(scanf("%d", &n)==1) {
        for(int i=1;i<=n;i++) gn(a[i]); ini();
        gn(m);
        int a, b;
        Node *af, *bf;
        while(m--) {
            gn(a), gn(b); af=Find(rt[a]), bf=Find(rt[b]);
            if(af==bf) printf("-1\n");
            else printf("%d\n", Merge(Reduce(af), Reduce(bf))->v);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1456.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆