[COI2009] OTOCI

Description

维护一个森林，支持连边、修改点权、询问路径点权和

Solution

基础的 LCT 点权信息维护

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

const int N = 100000;

int n,m,val[N];

namespace lct {
	int top, q[N], ch[N][2], fa[N], sum[N], rev[N];
	inline void pushup(int x){
		sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
	}
	inline void pushdown(int x){
		if(!rev[x]) return;
		rev[ch[x][0]]^=1;
		rev[ch[x][1]]^=1;
		rev[x]^=1;
		swap(ch[x][0],ch[x][1]);
	}
	inline bool isroot(int x){
		return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
	}
	inline void rotate(int p){
		int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;
		ch[q][x]=ch[p][x^1]; fa[ch[q][x]]=q;
		ch[p][x^1]=q; fa[q]=p; fa[p]=y;
		if(y) if(ch[y][0]==q) ch[y][0]=p;
		else  if(ch[y][1]==q) ch[y][1]=p;
		pushup(q); pushup(p);
	}
	inline void splay(int x){
		q[top=1]=x;
		for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
		for(int i=top;i;i--) pushdown(q[i]);
		for(;!isroot(x);rotate(x))
			if(!isroot(fa[x]))
				rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);
	}
	void access(int x){
		for(int t=0;x;t=x,x=fa[x])
			splay(x),ch[x][1]=t,pushup(x);
	}
	void makeroot(int x){
		access(x);
		splay(x);
		rev[x]^=1;
	}
	int find(int x){
		access(x);
		splay(x);
		while(ch[x][0]) x=ch[x][0];
		return x;
	}
	void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	void cut(int x,int y){
		split(x,y);
		if(ch[y][0]==x)
			ch[y][0]=0, fa[x]=0;
	}
	void link(int x,int y){
		makeroot(x);
		fa[x]=y;
	}
	void modify(int p,int x) {
        split(p,p);
        val[p]=x;
        pushup(p);
	}
	int islinked(int p,int q) {
        return find(p)==find(q);
	}
	int query(int p,int q) {
        split(p,q);
        return sum[q];
	}
}

signed main() {
    int t1,t2,t3,t4;
    ios::sync_with_stdio(false);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        char op[15];
        scanf("%s%d%d",op,&t1,&t2);
        if(op[0]=='b') {
            if(lct::islinked(t1,t2)) {
                cout<<"no"<<endl;
            }
            else {
                cout<<"yes"<<endl;
                lct::link(t1,t2);
            }
        }
        if(op[0]=='p') {
            lct::modify(t1,t2);
        }
        if(op[0]=='e') {
            if(lct::islinked(t1,t2)) {
                cout<<lct::query(t1,t2)<<endl;
            }
            else {
                cout<<"impossible"<<endl;
            }
        }
    }
}