ZOJ 3195 Design the city (lca + st )

ZOJ 3195 Design the city

给出n个区域，有n-1条路去连接这些区域，显然他是一个带权无根树。首先把它以0为根看成有根树，对于给出的三个点，每两个点之间的距离是固定的，因为他们之间只有一条路，但是对于这么多查询（at most 70000 ),直接找距离代价太大，找出每两个点的LCA，这样就可以两个点之间的距离了，（需要知道从0点开始到这两个点的距离）。 我们把这三对点的距离加起来再除以2，就能得到连接着三个点的最短路径。

#include<string>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<climits>
#include<map>
#include<vector>
const int maxn = 50000;
using namespace std;
class Node{
public:
    int to,w;
    Node *next;
    void add( int tt,int ww,Node *&b ){
        to = tt;w= ww;next = b;b=this;
    }
};
int ab(int a,int b){return a>b?(a-b):(b-a);}
Node *biao[ maxn ],a[ maxn*3 ];
int TIME,countt,N;
int founder[ maxn ];
int timepoint[ maxn*2 ];
int timedeep [ maxn*2 ];
int opt[ maxn*2 ][ 20 ];
int flag[ maxn ];
int d[ maxn ];
int o[ 3 ];
void dfs( int u,int deep ){
    timedeep[ founder[u] = TIME++ ] = deep;
    timepoint[ TIME-1 ] = u;
    flag[u] = 1;
    for( Node*p=biao[u]; p != NULL; p = p->next )
        if( !flag[p->to] ){
            d[p->to] = d[u] + p->w;
            dfs( p->to , deep +1 );
            timepoint[TIME++] = u;
            timedeep[TIME-1]= deep;
        }
}
//这个dfs计算时间戳，顺便计算每个点到0点的距离
int main(void){
    int i,from,m,to,w;
    int j,tt,minn,countt;
    int start,end,k,s = 0;
    while( scanf("%d",&N) != EOF ){
        if( s++ ) cout << endl;
        for( i = 0; i < N; i++ )
            biao[i] = NULL;
        countt = 0;
        for( i = 1; i < N; i++ ){
            scanf("%d%d%d",&from,&to,&w);
            a[countt++].add( to,w,biao[from] );
            a[countt++].add( from,w,biao[to] );
        }

        for( i = 0; i < N; i++ )
            flag[i]  = 0;
        d[0] = 0;
        TIME = 0;
        dfs( 0,0 );

        for( i = 0; i < 2*N -1 ; i++ )
            opt[i][0] = i;

        for( j = 1; (1<<j) <= 2*N-1; j++ ){
            tt = 1<<j;
            for( i = 0; i + tt -1 < 2*N -1 ; i++ ){
                if( timedeep[ opt[i][j-1] ] <
                    timedeep[ opt[i+tt/2][j-1] ] )
                    opt[i][j] = opt[i][j-1];
                else
                    opt[i][j] = opt[i+tt/2][j-1];
            }
        }
        //应该是st算法吧,这个dp实在是太神奇了。。
        cin >> m;
        while( m-- ){
            scanf("%d%d%d",&o[0],&o[1],&o[2]);
            minn = 0;
            for( i = 0; i < 3; i++ ){
                start = min( founder[o[i]], founder[o[(i+1)%3]] );
                end = max(   founder[o[i]], founder[o[(i+1)%3]] );

                k = (int)( log(end-start+1)/log(2) );

                if( timedeep[ opt[start][k] ] <
                    timedeep[ opt[end-(1<<k)+1][k] ] )
                    tt = opt[start][k] ;
                else
                    tt = opt[end-(1<<k)+1][k] ;

                k = d[ timepoint[start] ] - d[timepoint[tt]];
                k += d[timepoint[end] ] - d[timepoint[tt]];

                minn += k;
            }
            printf("%d\n",minn/2);
        }

    }
    return 0;
}