1180: [CROATIAN2009]OTOCI

Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 1032 Solved: 638
[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

HINT

Source

分析：

LCT板子...

询问A到B的路径上的权值和就是把A变成根节点然后询问B到根节点路径的权值和...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

const int maxn=30000+5;

int n,m;

char opt[13];

struct M{

	int val,sum;

	M *son[2],*father;

	bool reverse;

	inline M(int v=0){

		val=v,sum=v;

		son[0]=son[1]=NULL;

		father=NULL;

		reverse=false;

	}

	inline void update(void){

		sum=val;

		if(son[0]) sum+=son[0]->sum;

		if(son[1]) sum+=son[1]->sum;

	}

	inline bool isroot(void){

		if(father==NULL)

			return true;

		if(father->son[0]==this)

			return false;

		if(father->son[1]==this)

			return false;

		return true;

	}

	inline void pushdown(void){

		if(reverse){

			reverse=false;

			swap(son[0],son[1]);

			if(son[0]) son[0]->reverse^=true;

			if(son[1]) son[1]->reverse^=true;

		}

	}

}tr[maxn];

inline void connect(M *f,M *t,bool k){

	if(t!=NULL) t->father=f;

	if(f!=NULL) f->son[k]=t;

}

inline void rotate(M *t){

	M *f=t->father;

	M *g=f->father;

	bool s=(f->son[1]==t);

	connect(f,t->son[!s],s);

	connect(t,f,!s);

	t->father=g;

	if(g&&g->son[0]==f) g->son[0]=t;

	if(g&&g->son[1]==f) g->son[1]=t;

	f->update();

	t->update();

}

inline void push(M *t){

	static M *stk[maxn];

	int top=0;

	stk[top++]=t;

	while(!t->isroot())

		stk[top++]=t=t->father;

	while(top) stk[--top]->pushdown();

}

inline void splay(M *t){

	push(t);

	while(!t->isroot()){

		M *f=t->father;

		M *g=f->father;

		if(f->isroot())

			rotate(t);

		else{

			bool a=(f&&f->son[1]==t);

			bool b=(g&&g->son[1]==f);

			if(a==b)

				rotate(f),rotate(t);

			else

				rotate(t),rotate(t);

		}

	}

}

inline void access(M *t){

	M *p=NULL;

	while(t!=NULL){

		splay(t);

		t->son[1]=p,t->update();

		p=t,t=t->father;

	}

}

inline void makeroot(M *t){

	access(t),splay(t),t->reverse^=true;

}

inline void link(M *t,M *f){

	makeroot(t),t->father=f;

}

inline void cut(M *t){

	splay(t);

	if(t->son[0]) t->son[0]->father=NULL;

	if(t->son[1]) t->son[1]->father=NULL;

	t->son[0]=t->son[1]=NULL,t->update();

}

inline M *find(M *t){

	access(t);

	splay(t);

	M *r=t;

	while(r->son[0])

		r=r->son[0];

	return r;

}

signed main(void){

	scanf("%d",&n);

	for(int i=1,w;i<=n;i++)

		scanf("%d",&w),tr[i]=M(w);

	scanf("%d",&m);

	for(int q=1,x,y;q<=m;q++){

		scanf("%s%d%d",opt,&x,&y);

		if(opt[0]=='b'){

			if(find(tr+x)==find(tr+y))

				puts("no");

			else

				puts("yes"),link(tr+x,tr+y);

		}

		else if(opt[0]=='p'){

			access(tr+x),splay(tr+x);

			tr[x].val=y,tr[x].update();

		}

		else{

			if(find(tr+x)!=find(tr+y))

				puts("impossible");

			else

				makeroot(tr+x),access(tr+y),splay(tr+y),

				printf("%d\n",tr[y].sum);

		}

	}

	return 0;

}

By NeighThorn

巴特西

1180: [CROATIAN2009]OTOCI