动态树，支持加边，修改点权，查询链的点权和。
#include <cstdio>
#include <iostream>
#define maxn 30010
using namespace std; namespace L {
int pnt[maxn], pre[maxn], son[maxn][], val[maxn], sum[maxn], rtg[maxn]; void update( int nd ) {
sum[nd] = val[nd] + sum[son[nd][]] + sum[son[nd][]];
}
void rotate( int nd, int d ) {
int p = pre[nd];
int s = son[nd][!d];
int ss = son[s][d];
son[nd][!d] = ss;
son[s][d] = nd;
if( p ) son[p][ nd==son[p][] ] = s;
else pnt[s] = pnt[nd];
pre[nd] = s;
pre[s] = p;
pre[ss] = nd;
update( nd );
update( s );
}
void pushdown( int nd ) {
if( rtg[nd] ) {
int &ls = son[nd][], &rs = son[nd][];
swap(ls,rs);
rtg[ls] ^= ;
rtg[rs] ^= ;
rtg[nd] = ;
}
}
void big_push( int nd ) {
if( pre[nd] ) big_push(pre[nd]);
pushdown(nd);
}
void splay( int nd, int top= ) {
big_push(nd);
while( pre[nd]!=top ) {
int p = pre[nd];
int nl = nd==son[p][];
if( pre[p]==top ) {
rotate( p, nl );
} else {
int pp = pre[p];
int pl = p==son[pp][];
if( nl==pl ) {
rotate( pp, pl );
rotate( p, nl );
} else {
rotate( p, nl );
rotate( pp, pl );
}
}
}
}
void access( int nd ) {
int u = nd;
int v = ;
while( u ) {
splay( u );
int s = son[u][];
pre[s] = ;
pnt[s] = u;
pre[v] = u;
son[u][] = v;
update( u );
v = u;
u = pnt[u];
}
splay(nd);
}
void makeroot( int nd ) {
access(nd);
rtg[nd] ^= ;
}
int findroot( int nd ) {
while( pre[nd] ) nd=pre[nd];
while( pnt[nd] ) {
nd = pnt[nd];
while( pre[nd] ) nd=pre[nd];
}
return nd;
}
bool sameroot( int u, int v ) {
return findroot(u)==findroot(v);
}
void link( int u, int v ) {
makeroot(u);
makeroot(v);
pnt[u] = v;
}
void up_val( int nd, int v ) {
splay( nd );
val[nd] = v;
update( nd );
}
int qu_sum( int u, int v ) {
makeroot(u);
access(v);
return val[v]+sum[son[v][]];
}
}; int n, q; int main() {
scanf( "%d", &n );
for( int i=, w; i<=n; i++ ) {
scanf( "%d", &w );
L::up_val( i, w );
}
scanf( "%d", &q );
while( q-- ) {
char ch[];
int u, v, w;
scanf( "%s", ch );
if( ch[]=='b' ) {
scanf( "%d%d", &u, &v );
if( L::sameroot(u,v) ) printf( "no\n" );
else {
printf( "yes\n" );
L::link(u,v);
}
} else if( ch[]=='p' ) {
scanf( "%d%d", &u, &w );
L::up_val( u, w );
} else {
scanf( "%d%d", &u, &v );
if( L::sameroot(u,v) )
printf( "%d\n", L::qu_sum(u,v) );
else
printf( "impossible\n" );
}
}
}