Uva1553 Caves and Tunnels LCT

  1 #include <cstdio>
  2 #include <iostream>
  3 #define maxn 100010
  4 using namespace std;
  5 
  6 namespace L {
  7     int pnt[maxn], pre[maxn], son[maxn][2], rtg[maxn], val[maxn], mxv[maxn];
  8 
  9     inline void update( int nd ) {
 10         mxv[nd] = max( val[nd], max(mxv[son[nd][0]],mxv[son[nd][1]]) );
 11     }
 12     void rotate( int nd, int d ) {
 13         int p = pre[nd];
 14         int s = son[nd][!d];
 15         int ss = son[s][d];
 16         son[nd][!d] = ss;
 17         son[s][d] = nd;
 18         if( p ) son[p][ nd==son[p][1] ] = s;
 19         else pnt[s] = pnt[nd];
 20         pre[nd] = s;
 21         pre[ss] = nd;
 22         pre[s] = p;
 23         update(nd);
 24         update(s);
 25     }
 26     void pushdown( int nd ) {
 27         if( rtg[nd] ) {
 28             int &ls=son[nd][0], &rs=son[nd][1];
 29             swap(ls,rs);
 30             rtg[ls] ^= 1;
 31             rtg[rs] ^= 1;
 32             rtg[nd] = 0;
 33         }
 34     }
 35     void bigpush( int nd ) {
 36         if( pre[nd] ) bigpush(pre[nd]);
 37         pushdown(nd);
 38     }
 39     void splay( int nd, int top=0 ) {
 40         bigpush(nd);
 41         while( pre[nd]!=top ) {
 42             int p = pre[nd];
 43             int nl = nd==son[p][0];
 44             if( pre[p]==top ) {
 45                 rotate( p, nl );
 46             } else {
 47                 int pp = pre[p];
 48                 int pl = p==son[pp][0];
 49                 if( nl==pl ) {
 50                     rotate( pp, pl );
 51                     rotate( p, nl );
 52                 } else {
 53                     rotate( p, nl );
 54                     rotate( pp, pl );
 55                 }
 56             }
 57         }
 58     }
 59     void access( int nd ) {
 60         int u = nd;
 61         int v = 0;
 62         while( u ) {
 63             splay(u);
 64             int s = son[u][1];
 65             pre[s] = 0;
 66             pnt[s] = u;
 67             pre[v] = u;
 68             son[u][1] = v;
 69             update(u);
 70             v = u;
 71             u = pnt[u];
 72         }
 73         splay(nd);
 74     }
 75     void init( int n ) {
 76         for( int i=0; i<=n; i++ )
 77             pnt[i] = pre[i] = son[i][0] = son[i][1] 
 78                 = rtg[i] = val[i] = mxv[i] = 0;
 79     }
 80     void makeroot( int nd ) {
 81         access(nd);
 82         rtg[nd] ^= 1;
 83     }
 84     void link( int u, int v ) {
 85         makeroot(u);
 86         makeroot(v);
 87         pnt[u] = v;
 88     }
 89     void inc_val( int nd, int w ) {
 90         splay( nd );
 91         val[nd] += w;
 92         update( nd );
 93     }
 94     int qu_max( int u, int v ) {
 95         makeroot(u);
 96         access(v);
 97         return max( val[v], mxv[son[v][0]] );
 98     }
 99 };
100 
101 int n, q;
102 
103 int main() {
104     scanf( "%d", &n );
105     L::init(n);
106     for( int i=2,u,v; i<=n; i++ ) {
107         scanf( "%d%d", &u, &v );
108         L::link(u,v);
109     }
110     scanf( "%d", &q );
111     while( q-- ) {
112         char ch[10];
113         int u, v, w;
114         scanf( "%s", ch );
115         if( ch[0]==‘I‘ ) {
116             scanf( "%d%d", &u, &w );
117             L::inc_val(u,w);
118         } else {
119             scanf( "%d%d", &u, &v );
120             printf( "%d\n", L::qu_max(u,v) );
121         }
122     }
123 }