spoj 375 query on a tree LCT

这道题是树链剖分的裸题，正在学LCT，用LCT写了，发现LCT代码比树链剖分还短点（但我的LCT跑极限数据用的时间大概是kuangbin大神的树链剖分的1.6倍，所以在spoj上是850ms卡过的）。

收获：

　　1、边转换成点（即若存在边(u,v)，则新加一个点z代表边，将z连接u和v，z的点权就是(u,v)的边权，非边点的权设为-oo），然后对边权的统计就变成了对点权的统计（这是LCT中处理边信息的通法之一）。

　　2、若要连接两个点u,v，先让它们分别称为根，然后将其中一个的path-parent设为另一个。

　　3、若要查找(u,v)的边点，运用“夹逼法”，先让两个点在一条重链上（即同一棵splay树），再splay(u,0)和splay(v,u)，这样v的一个子树就是边点（具体来说，可以先让u成为根，再access(v)，splay(u,0),splay(v,u)，此时v的左儿子必定是边点）

 #include <cstdio>

 #include <iostream>

 #define maxn 20010

 #define oo 0x3f3f3f3f

 #define max(a,b) ((a)>(b)?(a):(b))

 using namespace std;

 struct LCT {

     int pnt[maxn], pre[maxn], son[maxn][], val[maxn], mxv[maxn], ntot;

     bool tag[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[s] = p;

         if( ss ) pre[ss] = nd;

         update( nd );

         update( s );

     }

     inline void pushdown( int nd ) {

         if( tag[nd] ) {

             int &ls = son[nd][], &rs = son[nd][];

             swap( ls, rs );

             tag[ls] ^= ;

             tag[rs] ^= ;

             tag[nd] = ;

         }

     }

     void splay( int nd, int top= ) {

         static int stk[maxn], spt;

         int u = nd;

         for( spt=; u; u=pre[u] )

             stk[spt++] = u;

         while( spt-- )

             pushdown( stk[spt] );

         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 init( int n ) {

         for( int i=; i<=n; i++ ) {

             pre[i] = pnt[i] = son[i][] = son[i][] = tag[i] = ;

             mxv[i] = val[i] = -oo;

         }

     }

     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;

             v = u;

             u = pnt[u];

         }

         splay( nd );

     }

     void makeroot( int nd ) {

         access( nd );

         tag[nd] ^= ;

     }

     void link( int u, int v ) {

         makeroot(u);

         makeroot(v);

         pnt[u] = v;

     }

     void modify( int e, int w ) {

         splay(e);

         val[e] = w;

         update( e );

     }

     int query( int u, int v ) {

         makeroot(u);

         access(v);

         return max(val[v],mxv[son[v][]]);

     }

 };

 int n;

 LCT LT;

 int main() {

     int T;

     scanf( "%d", &T );

     while( T-- ) {

         scanf( "%d", &n );

         LT.init(n+n-);

         for( int i=,u,v,w; i<n; i++ ) {

             scanf( "%d%d%d", &u, &v, &w );

             LT.modify( n+i, w );

             LT.link( u, n+i );

             LT.link( v, n+i );

         }

         while() {

             char ch[];

             scanf( "%s", ch );

             if( ch[]=='Q' ) {

                 int u, v;

                 scanf( "%d%d", &u, &v );

                 printf( "%d\n", LT.query(u,v) );

             } else if( ch[]=='C' ) {

                 int e, w;

                 scanf( "%d%d", &e, &w );

                 LT.modify( n+e, w );

             } else break;

         }

     }

 }

巴特西

spoj 375 query on a tree LCT

最新文章

热门文章