直接放代码，记得开 O2 优化。

const int N = 300010;
namespace LCT
{
    struct node
    {
        int fa, ch[2];
        bool rev;
        int sz, sum, val;
    } nodes[N];
    void pushup(int x) 
    { 
        nodes[x].sz = nodes[nodes[x].ch[0]].sz + 1 + nodes[nodes[x].ch[1]].sz; 
        nodes[x].sum = nodes[nodes[x].ch[0]].sum + nodes[x].val + nodes[nodes[x].ch[1]].sum;
    }
    bool nroot(int x) { return nodes[nodes[x].fa].ch[0] == x || nodes[nodes[x].fa].ch[1] == x; }
    bool son(int x) { return nodes[nodes[x].fa].ch[1] == x; }
    void rotate(int x)
    {
        bool f = son(x);
        int y = nodes[x].fa, z = nodes[y].fa, w = nodes[x].ch[f ^ 1];
        if (nroot(y))
            nodes[z].ch[son(y)] = x;
        nodes[x].fa = z, nodes[x].ch[f ^ 1] = y;
        nodes[y].fa = x, nodes[y].ch[f] = w;
        if (w)
            nodes[w].fa = y;
        pushup(y), pushup(x);
    }

    void reverse(int x)
    {
        std::swap(nodes[x].ch[0], nodes[x].ch[1]);
        nodes[x].rev ^= 1;
    }
    void pushdown(int x)
    {
        if (nodes[x].rev)
        {
            if (nodes[x].ch[0])
                reverse(nodes[x].ch[0]);
            if (nodes[x].ch[1])
                reverse(nodes[x].ch[1]);
            nodes[x].rev = 0;
        }
    }
    void pushdown_all(int x)
    {
        if (nroot(x))
            pushdown_all(nodes[x].fa);
        pushdown(x);
    }
    void Splay(int x)
    {
        pushdown_all(x);
        while (nroot(x))
        {
            if (nroot(nodes[x].fa))
                rotate(son(x) == son(nodes[x].fa) ? nodes[x].fa : x);
            rotate(x);
        }
    }
    int access(int x)
    {
        int y;
        for (y = 0; x; y = x, x = nodes[x].fa)
            Splay(x), nodes[x].ch[1] = y, pushup(x);
        return y;
    }
    int findroot(int x)
    {
        access(x), Splay(x);
        while (nodes[x].ch[0])
            x = nodes[x].ch[0];
        return Splay(x), x;
    }
    bool connected(int x, int y) { return findroot(x) == findroot(y); }
    void makeroot(int x) { access(x), Splay(x), reverse(x); }
    void link(int x, int y)
    {
        // assert(!connected(x, y));
        makeroot(x);
        if (findroot(y) ^ x) // ignore connected
            nodes[x].fa = y;
    }
    void split(int x, int y) { makeroot(x), access(y), Splay(y); }
    void cut(int x, int y)
    {
        split(x, y);
        if (nodes[y].ch[0] == x && !nodes[x].ch[1])
            nodes[y].ch[0] = nodes[x].fa = 0, pushup(y);
    }
    int LCA(int x, int y) { return access(x), access(y); }
    void modify(int x, int v) { makeroot(x), nodes[x].val = v, pushup(x); }
    int route(int x, int y) { return split(x, y), nodes[y].sum; }
}
int n, q, x, u, v;
char s[15];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &x), LCT::modify(i, x);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%s%d%d", s, &u, &v);
        switch (s[0])
        {
        case 'b':
            puts(LCT::connected(u, v) ? "no" : "yes"), LCT::link(u, v);
            break;
        case 'p':
            LCT::modify(u, v);
            break;
        case 'e':
            if (LCT::connected(u, v))
                printf("%d\n", LCT::route(u, v));
            else
                puts("impossible");
        default:
            break;
        }
    }
}