Old style .. .

gistfile1.cpp

/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define Rush int T____; RD(T____); DO(T____)
#pragma comment(linker, "/STACK:36777216")
#pragma GCC optimize ("O2")

template<class T> inline void RD(T &);
inline int RD(){ int x; RD(x); return x;}
template<class T> inline void OT(const T &);
template<class T> inline T& _RD(T &x){ RD(x); return x;}
inline void RS(char *s){scanf("%s", s);}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void CLR(T &A){A.clear();}
template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}
inline int _1(int i){return 1<<i;}
template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
template<class T> inline void OT(const T &x){printf("%d\n", x);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
/* .................................................................................................................................. */
const int N = 30010;

int l[N], r[N], p[N], val[N], sum[N], rev[N]; int rt[N];
// Link-cut tree
int n;

#define lx l[x]
#define rx r[x]

inline int sgn(int x){
    return l[p[x]] == x ? 0 : r[p[x]] == x ? 1 : -1;
}

inline void Release(int x){
    if (rev[x]){
        swap(lx, rx);
        rev[lx] ^= 1, rev[rx] ^= 1;
        rev[x] = 0;
    }
}

inline void Update(int x){
    sum[x] = sum[lx] + sum[rx] + val[x];
}

inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}

#define z p[y]
inline void Rotate(int x){
    int y = p[x];

    if (sgn(y) != -1) /*Release(z),*/ Set(y == l[z] ? l : r, z, x);
    else p[x] = z;

    Release(y), Release(x);

    if (x == l[y]) Set(l, y, rx), Set(r, x, y);
    else Set(r, y, lx), Set(l, x, y);

    if (rt[y]) rt[y] = false, rt[x] = true; //rt[0] = true;
    Update(y); //Update(x);
}

inline void Splay(int x){
    while (sgn(x) != -1) Rotate(x);
    //Update(x);
}

int Access(int x){
    int y = 0; do{
        Splay(x), Release(x);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
    return y;
}

inline int Root(int x) {
    for (x=Access(x);Release(x),lx; x=lx);
    return x;
}

inline void Evert(int x) {
    rev[Access(x)] ^= 1;
}

// Public :

void Link(int x, int y){
    if (Root(x) == Root(y)){
        puts("no");
    }
    else {
        Evert(x), Splay(x), p[x] = y, Access(x);
        puts("yes");
    }
}

void Modify(int x, int v){
    //Access(x),
    Splay(x), val[x] = v;
    // Update(x);
}

void Query(int x, int y){
    if (Root(x) != Root(y)){
        puts("impossible");
    }
    else {
        Access(y); y = 0; do{                   //sum[x] - sum[lx] + sum[y]
            Splay(x), Release(x); if (!p[x]) OT(sum[rx] + val[x] + sum[y]);
            rt[rx] = true, rt[rx = y] = false, Update(x);
            x = p[y = x];
        } while (x);
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif


    REP_1_C(i, _RD(n)) RD(val[i]); // rt[i] = 1;

    int a, b; char cmd[19]; Rush{
        RS(cmd); RD(a, b); if (cmd[0] == 'e') Query(a, b);
        else if (cmd[0] == 'b') Link(a, b);
        else Modify(a, b);
    }
}