bzoj 1468

大概思路：树点分治，重心树中每个重心维护一个总的平衡树，树中保存属于该重心的点到该重心的距离，然后对于去掉该重心后形成的子树分别再保存一份。

用这种方式实现的话，还可以支持修改与多次查询，每次操作都是O(logn*logn)

感悟：

点分治正如一个前辈说的，是“借助”重心的力量，来维护与查询与某点距离相关的问题，我们知道点u到它各个重心的距离关系，各个重心又保存了所有属于它的点的信息，可以证明，一个点至多属于O(logn)个重心，所有重心拥有的点总和为O(nlogn)。

本质上来说，树的点分治是通过找重心来对树分治，然后建立了一种层次关系（想象一下，找出一棵树的重心，然后在3维空间向上提升，幷让重心向剩下的各块的重心连边，然后再将各块分层，这样就形成了这种层次关系，表现为树结构就是所谓的重心树）。

 /**************************************************************

     Problem: 1468

     User: idy002

     Language: C++

     Result: Accepted

     Time:6536 ms

     Memory:54384 kb

 ****************************************************************/

 #include <cstdio>

 #include <vector>

 #include <map>

 #define fprintf(...)

 #define N 40010

 #define S 2000000

 using namespace std;

 struct Stat {

     int c, d, s;

     Stat( int c, int d, int s ):c(c),d(d),s(s){}

 };

 struct Splay {

     static int son[S][], pre[S], key[S], siz[S], ntot;

     int root;

     void init() { root=; }

     inline void update( int nd ) {

         siz[nd] = siz[son[nd][]]+siz[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 root = s;

         pre[nd] = s;

         pre[s] = p;

         if( ss ) pre[ss] = nd;

         update( nd );

         update( s );

     }

     void splay( int nd, int top= ) {

         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 );

                 }

             }

         }

     }

     int newnode( int p, int k ) {

         int nd = ++ntot;

         son[nd][] = son[nd][] = ;

         pre[nd] = p;

         key[nd] = k;

         siz[nd] = ;

         return nd;

     }

     void insert( int k ) {

         if( !root ) {

             root = newnode( , k );

             return;

         }

         int nd = root;

         while( son[nd][ k>key[nd] ] ) nd=son[nd][ k>key[nd] ];

         son[nd][ k>key[nd] ] = newnode( nd, k );

         splay( son[nd][ k>key[nd] ] );

     }

     int query( int k ) {

         int nd=root;

         int lnd;

         int rt = ;

         while(nd) {

             lnd = nd;

             if( key[nd]>k ) {

                 nd = son[nd][];

             } else {

                 rt += siz[son[nd][]]+;

                 nd = son[nd][];

             }

         }

         splay( lnd );

         return rt;

     }

 };

 int Splay::son[S][], Splay::pre[S], Splay::key[S], Splay::siz[S], Splay::ntot;

 int n, qdis;

 vector<int> g[N], ww[N];

 vector<Stat> st[N];

 map<int,Splay > spy[N];

 int vis[N], anc[N], siz[N], bac[N], dis[N];

 int qu[N], bg, ed;

 void build( int rt ) {

     /* find the core of the block containing rt */

     qu[bg=ed=] = rt;

     anc[rt] = rt;

     siz[rt] = bac[rt] = ;

     while( ed>=bg ) {

         int u=qu[bg++];

         for( int t=; t<g[u].size(); t++ ) {

             int v=g[u][t];

             if( vis[v] || v==anc[u] ) continue;

             qu[++ed] = v;

             anc[v] = u;

             siz[v] = bac[v] = ;

         }

     }

     for( int i=ed; i>=; i-- ) {

         int u=qu[i];

         int p=anc[u];

         siz[u]++;

         siz[p] += siz[u];

         if( bac[p]<siz[u] ) bac[p]=siz[u];

     }

     for( int i=ed; i>=; i-- ) {

         int u=qu[i];

         if( bac[u]<siz[rt]-siz[u] ) bac[u]=siz[rt]-siz[u];

     }

     for( int i=ed; i>=; i-- ) {

         int u=qu[i];

         if( bac[u]<bac[rt] ) rt=u;

     }

     /* statistics the info of the block */

     spy[rt][].init();

     spy[rt][].insert(  );

     st[rt].push_back( Stat(rt,,) );

     vis[rt] = true;

     fprintf( stderr, "%d as core\n", rt );

     for( int tm=; tm<g[rt].size(); tm++ ) {

         int r=g[rt][tm], w=ww[rt][tm];

         if( vis[r] ) continue;

         qu[bg=ed=] = r;

         anc[r] = rt;

         dis[r] = w;

         while( ed>=bg ) {

             int u=qu[bg++];

             for( int t=; t<g[u].size(); t++ ) {

                 int v=g[u][t], w=ww[u][t];

                 if( vis[v] || v==anc[u] ) continue;

                 qu[++ed] = v;

                 anc[v] = u;

                 dis[v] = dis[u]+w;

             }

         }

         spy[rt][r].init();

         for( int i=ed; i>=; i-- ) {

             int u=qu[i];

             spy[rt][].insert( dis[u] );

             spy[rt][r].insert( dis[u] );

             st[u].push_back( Stat(rt,dis[u],r) );

         }

         build( r );

     }

 }

 int main() {

     scanf( "%d", &n );

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

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

         g[u].push_back( v );

         g[v].push_back( u );

         ww[u].push_back( w );

         ww[v].push_back( w );

     }

     scanf( "%d", &qdis );

     build();

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

         fprintf( stderr, "Stat of %d:\n", u );

         for( int t=; t<st[u].size(); t++ ) {

             fprintf( stderr, "core=%d dis=%d subcore:%d\n", st[u][t].c, st[u][t].d, st[u][t].s );

         }

         fprintf( stderr, "\n" );

     }

     int ans = ;

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

         int tans=;

         for( int t=; t<st[u].size(); t++ ) {

             Stat &s = st[u][t];

             tans += spy[s.c][].query( qdis-s.d )- (s.s?spy[s.c][s.s].query( qdis-s.d ):);

         }

         fprintf( stderr, "%d added %d\n", u, tans- );

         ans += tans-;

     }

     printf( "%d\n", ans/ );

 }

巴特西

bzoj 1468

最新文章

热门文章