How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4702 Accepted Submission(s): 1765
Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to
answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road
connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road
connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1
Sample Output
10 25 100 100
Source
ECJTU 2009 Spring Contest
题型：LCA求树上两点最近距离。
题目大意：
给你一颗n个点的树，树边有权值k，m次询问，每次问(u,v)路径上的权值和最小的路的最小权值和。( 2 <= n <= 40000 , 1 <= m <= 200 , 0 < k <= 40000)。
题目分析：
不知道是不是在线LCA效率有点低？反正效率一般。
我有两种基于倍增的实现方法（个人感觉第二种更好）。
每种都需要先将无根树转化成有根树。这里我们假设已经转化完成。
一：预处理出每个点ｉ与其2^j级祖先的路径权值和。然后在倍增算法中累加即可。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define LOGF( i , n ) for ( int i = 1 ; ( 1 << i ) < n ; ++ i )
#define EDGE( i , x ) for ( int i = adj[x] ; ~i ; i = edge[i].n )
#define clear( a , x ) memset ( a , x , sizeof a )
const int MAXN = 40005 ;
const int MAXE = 80005 ;
const int LOGN = 20 ;
struct Edge {
int v , w , n ;
Edge ( int var = 0 , int cost = 0 , int next = 0 ) :
v ( var ) , w ( cost ) , n ( next ) {}
} ;
struct LCA {
Edge edge[MAXE] ;
int adj[MAXN] , cntE ;
int deep[MAXN] ;
int cost[MAXN] ;
int anc[MAXN][LOGN] ;
int fa[MAXN] ;
int totcost[MAXN][LOGN] ;
int n ;
void init () {
clear ( adj , -1 ) ;
cntE = 0 ;
}
void addedge ( int u , int v , int w ) {
edge[cntE] = Edge ( v , w , adj[u] ) ;
adj[u] = cntE ++ ;
edge[cntE] = Edge ( u , w , adj[v] ) ;
adj[v] = cntE ++ ;
}
void dfs ( int u , int p ) {
EDGE ( i , u ) {
int v = edge[i].v ;
if ( v != p ) {
fa[v] = u ;
deep[v] = deep[u] + 1 ;
cost[v] = edge[i].w ;
dfs( v , u ) ;
}
}
}
void preProcess () {
REPF ( i , 1 , n ) {
anc[i][0] = fa[i] , totcost[i][0] = cost[i] ;
LOGF ( j , n )
anc[i][j] = -1 ;
}
LOGF ( j , n )
REPF ( i , 1 , n )
if ( ~anc[i][j - 1] ) {
int u = anc[i][j - 1] ;
totcost[i][j] = totcost[i][j - 1] + totcost[u][j - 1] ;
anc[i][j] = anc[u][j - 1] ;
}
}
int query ( int p , int q ) {
int log = 0 , ans = 0 ;
if ( deep[p] < deep[q] )
swap ( p , q ) ;
LOGF ( i , deep[p] + 1 )
++ log ;
REPV ( i , log , 0 )
if ( deep[p] - ( 1 << i ) >= deep[q] ) {
ans += totcost[p][i] ;
p = anc[p][i] ;
}
if ( p == q )
return ans ;
REPV ( i , log , 0 )
if ( ~anc[p][i] && anc[p][i] != anc[q][i] ) {
ans += totcost[p][i] + totcost[q][i] ;
p = anc[p][i] ;
q = anc[q][i] ;
}
ans += cost[p] + cost[q] ;
return ans ;
}
} ;
LCA L ;
void work () {
int u , v , w , m ;
scanf ( "%d%d" , &L.n , &m ) ;
L.init () ;
REPF ( i , 1 , L.n - 1 ) {
scanf ( "%d%d%d" , &u , &v , &w ) ;
L.addedge ( u , v , w ) ;
}
L.dfs ( 1 , 0 ) ;
L.preProcess () ;
while ( m -- ) {
scanf ( "%d%d" , &u , &v ) ;
printf ( "%d\n" , L.query ( u , v ) ) ;
}
}
int main () {
int T ;
scanf ( "%d" , &T ) ;
while ( T -- )
work () ;
return 0 ;
}
二：直接dfs中计算得到每个点ｉ到根结点的路径权值和dist[ i ]，设询问的点对为(u,v)，则(u,v)的最近公共祖先就是lca(u,v)，那么答案ans = dist[ u ] + dist[ v ] - 2 * dist[ lca (u,v) ] 。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define LOGF( i , n ) for ( int i = 1 ; ( 1 << i ) < n ; ++ i )
#define EDGE( i , x ) for ( int i = adj[x] ; ~i ; i = edge[i].n )
#define clear( a , x ) memset ( a , x , sizeof a )
const int MAXN = 40005 ;
const int MAXE = 80005 ;
const int LOGN = 20 ;
struct Edge {
int v , w , n ;
Edge ( int var = 0 , int cost = 0 , int next = 0 ) :
v ( var ) , w ( cost ) , n ( next ) {}
} ;
struct LCA {
Edge edge[MAXE] ;
int adj[MAXN] , cntE ;
int deep[MAXN] ;
int dist[MAXN] ;
int anc[MAXN][LOGN] ;
int fa[MAXN] ;
int n ;
void init () {
clear ( adj , -1 ) ;
cntE = 0 ;
}
void addedge ( int u , int v , int w ) {
edge[cntE] = Edge ( v , w , adj[u] ) ;
adj[u] = cntE ++ ;
edge[cntE] = Edge ( u , w , adj[v] ) ;
adj[v] = cntE ++ ;
}
void dfs ( int u , int p ) {
EDGE ( i , u ) {
int v = edge[i].v ;
if ( v != p ) {
fa[v] = u ;
deep[v] = deep[u] + 1 ;
dist[v] = dist[u] + edge[i].w ;
dfs( v , u ) ;
}
}
}
void preProcess () {
REPF ( i , 1 , n ) {
anc[i][0] = fa[i] ;
LOGF ( j , n )
anc[i][j] = -1 ;
}
LOGF ( j , n )
REPF ( i , 1 , n )
if ( ~anc[i][j - 1] ) {
int u = anc[i][j - 1] ;
anc[i][j] = anc[u][j - 1] ;
}
}
int query ( int p , int q ) {
int log = 0 ;
if ( deep[p] < deep[q] )
swap ( p , q ) ;
LOGF ( i , deep[p] + 1 )
++ log ;
REPV ( i , log , 0 )
if ( deep[p] - ( 1 << i ) >= deep[q] ) {
p = anc[p][i] ;
}
if ( p == q )
return p ;
REPV ( i , log , 0 )
if ( ~anc[p][i] && anc[p][i] != anc[q][i] ) {
p = anc[p][i] ;
q = anc[q][i] ;
}
return fa[p] ;
}
} ;
LCA L ;
void work () {
int u , v , w , m ;
scanf ( "%d%d" , &L.n , &m ) ;
L.init () ;
REPF ( i , 1 , L.n - 1 ) {
scanf ( "%d%d%d" , &u , &v , &w ) ;
L.addedge ( u , v , w ) ;
}
L.dist[1] = 0 ;
L.dfs ( 1 , 0 ) ;
L.preProcess () ;
while ( m -- ) {
scanf ( "%d%d" , &u , &v ) ;
printf ( "%d\n" , L.dist[u] + L.dist[v] - 2 * L.dist[L.query ( u , v )] ) ;
}
}