<div class="post_brief"><p>
难得的水水的双倍题。</p>

 

看上去是想考lct然后忘强制在线了么？那就直接预处理出形态然后链剖呗。当然我还没有达到mhy这种认为lct比tcd好写的水平。

 

中间还把修改写挂了一次，然后1180的询问数是2843的3倍又re了一次。晕。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


struct edge {
int t;
edge *next;
};
struct seg {
int l, r, s[2];
seg *ls, *rs;
};
struct query {
char o;
int a, b, s;
};


const int maxn = 30009;
const int maxm = 300009;


int n, m, r[maxn], d[maxn], v[maxn], u[maxn];
int fa[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn];
int qret[2];
seg slst[maxn << 2], *sp(slst), *rt[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
query q[maxm];


inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}


int getRoot(int x) {
register int p, q;
for (p = r[x]; r[p] ^ p; p = r[p]);
for (; x ^ p; q = r[x], r[x] = p, x = q);
return x;
}


void divide(int p0) {
static int q[maxn];
int hd(0), tl(1);
q[0] = p0;
d[p0] = 1;
fa[p0] = 0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (e-> t != fa[p]) {
d[e-> t] = d[p] + 1;
fa[e-> t] = p;
q[tl ++] = e-> t;
}
}
for (int i = tl - 1; i >= 0; – i) {
int p(q[i]), z(-1);
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t != fa[p]) {
sz[p] += sz[e-> t];
if (z == -1 || sz[e-> t] > sz[z])
z = e-> t;
}
if (z == -1)
cl[fc[p] = ++ tc] = 1;
else
++ cl[fc[p] = fc[z]];
ch[fc[p]] = p;
}
}


#define cpos(p) (d[p]-d[ch[fc[p]]])
#define midp(p) ((p->l+p->r)>>1)


inline seg* sgtBuild(int l, int r) {
seg* p(sp ++);
p-> l = l;
p-> r = r;
p-> s[0] = r - l;
p-> s[1] = 0;
if (l + 1 < r) {
p-> ls = sgtBuild(l, midp(p));
p-> rs = sgtBuild(midp(p), r);
}
return p;
}
inline void sgtChg(seg* p, int p0, int i, int v) {
if (p-> l + 1 == p-> r)
p-> s[i] = v;
else {
if (p0 < midp(p))
sgtChg(p-> ls, p0, i, v);
else
sgtChg(p-> rs, p0, i, v);
p-> s[i] = p-> ls-> s[i] + p-> rs-> s[i];
}
}
inline void sgtQry(seg* p, int l, int r) {
if (p-> l == l && p-> r == r) {
qret[0] += p-> s[0];
qret[1] += p-> s[1];
}
else if (r <= midp(p))
sgtQry(p-> ls, l, r);
else if (l >= midp(p))
sgtQry(p-> rs, l, r);
else {
sgtQry(p-> ls, l, midp(p));
sgtQry(p-> rs, midp(p), r);
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d", &amp;n);
for (int i = 1; i &lt;= n; ++ i) {
	r[i] = i;
	scanf("%d", v + i);
	u[i] = 1;
}
scanf("%d", &amp;m);
for (int i = 0; i &lt; m; ++ i) {
	char opt[11];
	scanf("%s%d%d", opt, &amp;q[i]. a, &amp;q[i]. b);
	q[i]. o = opt[0];
	if (q[i]. o == 'b') {
		if (getRoot(q[i]. a) ^ getRoot(q[i]. b)) {
			q[i]. s = 1;
			r[getRoot(q[i]. a)] = getRoot(q[i]. b);
			addEdge(q[i]. a, q[i]. b);
			addEdge(q[i]. b, q[i]. a);
		}
		else {
			q[i]. s = 0;
		}
	}
}
memset(d, 0, sizeof(d));
tc = 0;
for (int i = 1; i &lt;= n; ++ i)
	if (!d[i])
		divide(i);
for (int i = 1; i &lt;= tc; ++ i)
	rt[i] = sgtBuild(0, cl[i]);
for (int i = 1; i &lt;= n; ++ i)
	sgtChg(rt[fc[i]], cpos(i), 1, v[i]);
for (int i = 0; i &lt; m; ++ i)
	if (q[i]. o == 'b') {
		if (q[i]. s) {
			if (d[q[i]. a] &gt; d[q[i]. b])
				swap(q[i]. a, q[i]. b);
			u[q[i]. b] = 0;
			sgtChg(rt[fc[q[i]. b]], cpos(q[i]. b), 0, 0);
			puts("yes");
		}
		else
			puts("no");
	}
	else if (q[i]. o == 'p') {
		sgtChg(rt[fc[q[i]. a]], cpos(q[i]. a), 1, q[i]. b);
	}
	else if (q[i]. o == 'e') {
		int u(q[i]. a), v(q[i]. b);
		if (getRoot(u) != getRoot(v)) {
			puts("impossible");
		}
		else {
			qret[0] = qret[1] = 0;
			while (fc[u] ^ fc[v]) {
				if (d[ch[fc[u]]] &gt; d[ch[fc[v]]]) {
					sgtQry(rt[fc[u]], 0, cpos(u) + 1);
					u = fa[ch[fc[u]]];
				}
				else {
					sgtQry(rt[fc[v]], 0, cpos(v) + 1);
					v = fa[ch[fc[v]]];
				}
			}
			if (d[u] &gt; d[v])
				swap(u, v);
			sgtQry(rt[fc[u]], cpos(u), cpos(v) + 1);
			qret[0] -= :: u[u];
			if (qret[0])
				puts("impossible");
			else
				printf("%d\n",  qret[1]);
		}
	}



}