1180: [CROATIAN2009]OTOCI

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1463 Solved: 941
[Submit][Status][Discuss]
Description
给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作：
1、bridge A B：询问结点A与结点B是否连通。
如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。
2、penguins A X：将结点A对应的权值wA修改为X。
3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。
否则输出结点A到结点B的路径上的点对应的权值的和。
给出q个操作，要求在线处理所有操作。
数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。
Input
第一行包含一个整数n(1<=n<=30000)，表示节点的数目。
第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。
第三行包含一个整数q(1<=n<=300000)，表示操作的数目。
以下q行，每行包含一个操作，操作的类别见题目描述。
任意时刻每个节点对应的权值都是1到1000的整数。
Output
输出所有bridge操作和excursion操作对应的输出，每个一行。

Sample Input
5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5
Sample Output
4
impossible
yes
6
yes
yes
15
yes
15
16

求两点之间和+断开+连接+单点修改。

很明显的LCT了，我们维护一下两点之间和即可。

但是注意这道题目比较毒瘤，如果连接输出no，不连接输出yes，相反的！！！！

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int n,m,a[N];
struct Link_Cut_Tree{
	int cnt,st[N];
	struct node{int ch[2],fa,val,re;}t[N];
	inline void push_up(int p){
		t[p].val=t[t[p].ch[0]].val+t[t[p].ch[1]].val+a[p];
	}
	inline void push_re(int p){swap(t[p].ch[0],t[p].ch[1]); t[p].re^=1;}
	inline void push_down(int p){
		if(t[p].re){
			if(t[p].ch[0])	push_re(t[p].ch[0]);
			if(t[p].ch[1])	push_re(t[p].ch[1]); t[p].re^=1;
		}
	}
	inline bool isroot(int x){return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;}
	inline void rotate(int x){
		int y=t[x].fa,z=t[y].fa,k=t[y].ch[1]==x,w=t[x].ch[!k];
		if(!isroot(y))	t[z].ch[t[z].ch[1]==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
		if(w)	t[w].fa=y; t[y].fa=x; t[x].fa=z;	push_up(y);
	}
	inline void splay(int x){
		cnt=1;	st[cnt]=x; int y=x;
		while(!isroot(y))	st[++cnt]=y=t[y].fa;
		while(cnt)	push_down(st[cnt--]);
		while(!isroot(x)){
			int y=t[x].fa,z=t[y].fa;
			if(!isroot(y))	rotate((t[y].ch[0]==x)^(t[z].ch[0]==y)?x:y);	rotate(x);
		}push_up(x);
	}
	inline void access(int x){
		for(int y=0;x;x=t[y=x].fa) splay(x),t[x].ch[1]=y,push_up(x); 
	}
	inline void makeroot(int x){access(x); splay(x); push_re(x);}
	inline int find(int x){
		access(x); splay(x); while(t[x].ch[0]) push_down(x),x=t[x].ch[0]; 
		splay(x);	return x;
	}
	inline void split(int x,int y){makeroot(x); access(y); splay(y);}
	inline void link(int x,int y){makeroot(x); if(find(y)!=x)	t[x].fa=y;}
	inline void cut(int x,int y){
		makeroot(x); 
		if(find(y)==x&&t[y].fa==x&&!t[y].ch[0]) t[y].fa=t[x].ch[1]=0,push_up(x);
	}
}tr;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	cin>>m; char op[15]; int x,y;
	while(m--){
		scanf("%s %d %d",op,&x,&y);
		if(op[0]=='e'){
			if(tr.find(x)!=tr.find(y))	puts("impossible");
			else	tr.split(x,y),printf("%d\n",tr.t[y].val);
		}else if(op[0]=='b'){
			if(tr.find(x)!=tr.find(y))	puts("yes"),tr.link(x,y);
			else	puts("no");
		}else if(op[0]=='p')	tr.splay(x),a[x]=y;
	}
	return 0;
}