传送门:【SPOJ】913 Query on a tree II
题目分析:LCA倍增算法的应用,求两点间距离是没问题的,重要的是求路径上第k个点,首先LCA一次,看这个点是在x到祖先的路径上还是y到祖先的位置上,然后继续用类似二分的思想求这个点即可。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define logn( i , a , b ) for ( int i = ( a ) ; ( 1 << i ) <= ( b ) ; ++ i ) #define repp( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define cpy( a , x ) memcpy ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 2 , n #define mid ( ( l + r ) >> 1 ) const int LOG = 20 ; const int MAXN = 10005 ; const int MAXE = 20005 ; struct Edge { int v , c ; Edge* next ; } E[MAXE] , *H[MAXN] , *edge ; int anc[MAXN][LOG] ; int dist[MAXN] ; int pre[MAXN] ; int dep[MAXN] ; int n ; void clear () { edge = E ; clr ( H , 0 ) ; clr ( dep , 0 ) ; clr ( dist , 0 ) ; } void addedge ( int u , int v , int c ) { edge -> v = v ; edge -> c = c ; edge -> next = H[u] ; H[u] = edge ++ ; edge -> v = u ; edge -> c = c ; edge -> next = H[v] ; H[v] = edge ++ ; } void dfs ( int u , int fa = -1 ) { pre[u] = fa ; repp ( e , H , u ) { int v = e -> v ; if ( v == fa ) continue ; dist[v] = dist[u] + e -> c ; dep[v] = dep[u] + 1 ; dfs ( v , u ) ; } } void preprocess () { FOR ( i , 1 , n ) anc[i][0] = pre[i] ; FOR ( i , 1 , n ) logn ( j , 1 , n ) anc[i][j] = -1 ; logn ( j , 1 , n ) FOR ( i , 1 , n ) if ( ~anc[i][j - 1] ) anc[i][j] = anc[anc[i][j - 1]][j - 1] ; } int lca ( int x , int y ) { if ( dep[x] < dep[y] ) swap ( x , y ) ; int log = 0 ; logn ( i , 1 , dep[x] ) ++ log ; rev ( i , log , 0 ) if ( dep[x] - ( 1 << i ) >= dep[y] ) x = anc[x][i] ; if ( x == y ) return x ; rev ( i , log , 0 ) if ( ~anc[x][i] && anc[x][i] != anc[y][i] ) { x = anc[x][i] ; y = anc[y][i] ; } return pre[x] ; } int kth ( int x , int y , int k ) { int cp = lca ( x , y ) ; if ( dep[x] - dep[cp] + 1 >= k ) { int deep = dep[x] - k + 1 , log = 0 ; logn ( i , 1 , dep[x] ) ++ log ; rev ( i , log , 0 ) if ( dep[x] - ( 1 << i ) >= deep ) x = anc[x][i] ; return x ; } else { int deep = k - ( dep[x] - dep[cp] ) + dep[cp] - 1 , log = 0 ; logn ( i , 1 , dep[y] ) ++ log ; rev ( i , log , 0 ) if ( dep[y] - ( 1 << i ) >= deep ) y = anc[y][i] ; return y ; } } void solve () { char s[10] ; int x , y , c ; clear () ; scanf ( "%d" , &n ) ; rep ( i , 1 , n ) { scanf ( "%d%d%d" , &x , &y , &c ) ; addedge ( x , y , c ) ; } dfs ( 1 ) ; preprocess () ; while ( scanf ( "%s" , s ) && s[1] != 'O' ) { if ( s[0] == 'D' ) { scanf ( "%d%d" , &x , &y ) ; int cp = lca ( x , y ) ; printf ( "%d\n" , dist[x] + dist[y] - 2 * dist[cp] ) ; } else { scanf ( "%d%d%d" , &x , &y , &c ) ; printf ( "%d\n" , kth ( x , y , c ) ) ; } } } int main () { int T ; scanf ( "%d" , &T ) ; while ( T -- ) solve () ; return 0 ; }