Uva1553 Caves and Tunnels LCT

简单题，主要为了练手。

 #include <cstdio>
 #include <iostream>
 #define maxn 100010
 using namespace std; namespace L {
     int pnt[maxn], pre[maxn], son[maxn][], rtg[maxn], val[maxn], mxv[maxn];     inline void update( int nd ) {
         mxv[nd] = max( val[nd], max(mxv[son[nd][]],mxv[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[ss] = nd;
         pre[s] = p;
         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 bigpush( int nd ) {
         if( pre[nd] ) bigpush(pre[nd]);
         pushdown(nd);
     }
     void splay( int nd, int top= ) {
         bigpush(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 init( int n ) {
         for( int i=; i<=n; i++ )
             pnt[i] = pre[i] = son[i][] = son[i][]
                 = rtg[i] = val[i] = mxv[i] = ;
     }
     void makeroot( int nd ) {
         access(nd);
         rtg[nd] ^= ;
     }
     void link( int u, int v ) {
         makeroot(u);
         makeroot(v);
         pnt[u] = v;
     }
     void inc_val( int nd, int w ) {
         splay( nd );
         val[nd] += w;
         update( nd );
     }
     int qu_max( int u, int v ) {
         makeroot(u);
         access(v);
         return max( val[v], mxv[son[v][]] );
     }
 }; int n, q; int main() {
     scanf( "%d", &n );
     L::init(n);
     for( int i=,u,v; i<=n; i++ ) {
         scanf( "%d%d", &u, &v );
         L::link(u,v);
     }
     scanf( "%d", &q );
     while( q-- ) {
         char ch[];
         int u, v, w;
         scanf( "%s", ch );
         if( ch[]=='I' ) {
             scanf( "%d%d", &u, &w );
             L::inc_val(u,w);
         } else {
             scanf( "%d%d", &u, &v );
             printf( "%d\n", L::qu_max(u,v) );
         }
     }
 }