[bzoj 2843] 极地旅行社

维护一个n个点的初始没有边的无向图, m个操作, 支持: - 查询a,b连通性并连一条边 (已连通则忽略) - 修改某点点权 - 查询a,b路径上点权之和, 或报告不连通

(1≤n≤3*10^4, 1≤m≤10^5, 点权是[0,1000]内的整数) 由于没有删除操作, 离线, 建出最终的树, 树链剖分即可. 也可以直接丢一个LCT.

const int N = 3e4;

struct Node {
	Node* ch[2], * fa;
	int t, v, sum;
	bool rev;
	
	Node();
	void setf(Node* f, int _t)
	{
		t = _t;
		fa = f;
		t >= 0 ? f->ch[t] = this : 0;
	}
	void reverse()
	{
		rev ^= 1;
		swap(ch[0], ch[1]);
		ch[0]->t = 0;
		ch[1]->t = 1;
	}
	void down()
	{
		if (rev) {
			rev = false;
			ch[0]->reverse();
			ch[1]->reverse();
		}
	}
	void up()
	{
		sum = v + ch[0]->sum + ch[1]->sum;
	}
} nodes[N+1], * nil = nodes;

Node::Node(): fa(0), t(-1), v(0), sum(0), rev(false)
{
	ch[0] = ch[1] = nil;
}

inline void rot(Node* y)
{
	Node* x = y->fa;
	int t = y->t;
	y->setf(x->fa, x->t);
	y->ch[t^1]->setf(x, t);
	x->setf(y, t^1);
	x->up();
}

void splay(Node* x)
{
	Node* y;
	static Node* S[N];
	int top = 0;
	for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
	for (y->down(); top; S[--top]->down()) ;
	
	while (x->t >= 0) {
		if ((y = x->fa)->t >= 0)
			rot(x->t ^ y->t ? x : y);
		rot(x);
	}
	x->up();
}

void access(Node* x)
{
	for (Node* y = nil; x; y = x, x = x->fa) {
		splay(x);
		x->ch[1]->t = -1;
		y->setf(x, 1);
		x->up();
	}
}

inline void make_root(Node* x)
{
	access(x);
	splay(x);
	x->reverse();
}

Node* get_root(Node* x)
{
	access(x);
	splay(x);
	while (x->ch[0] != nil) {
		//x->down();
		x = x->ch[0];
	}
	return x;
}

inline bool link(Node* x, Node* y)
{
	make_root(x);
	if (get_root(y) == x) return false;
	x->setf(y, -1);
	return true;
}

inline void modify(Node* x, int v)
{
	access(x);
	splay(x);
	x->v = v;
	x->up();
}

inline int query(Node* x, Node* y)
{
	make_root(x);
	return get_root(y) == x ? y->sum : -1;
}

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 1, n+1) {
		scanf("%d", &nodes[i].v);
		nodes[i].sum = nodes[i].v;
	}
	int m;
	scanf("%d", &m);
	while (m--) {
		char s[10];
		int x, y, ret;
		scanf("%s%d%d", s, &x, &y);
		switch (s[0]) {
		case 'b':
			puts(link(nodes+x, nodes+y) ? "yes" : "no");
			break;
		case 'p':
			modify(nodes+x, y);
			break;
		default:
			ret = query(nodes+x, nodes+y);
			if (ret == -1)
				puts("impossible");
			else
				printf("%d\n", ret);
		}
	}
	return 0;
}