题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586
LCA模版题。
RMQ+LCA：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> using namespace std;
const int MAXN = 4e4 + ;
typedef pair<int , int>P;
vector <P> G[MAXN];
int dep[MAXN] , dis[MAXN] , par[MAXN][] , ok[MAXN]; void init(int n) {
for(int i = ; i <= n ; i++) {
G[i].clear();
ok[i] = ;
}
} void dfs(int root) {
for(int i = ; i < G[root].size() ; i++) {
dis[G[root][i].first] = dis[root] + G[root][i].second;
dfs(G[root][i].first);
}
} void dfs2(int u , int p , int d) {
dep[u] = d;
par[u][] = p;
for(int i = ; i < G[u].size() ; i++) {
dfs2(G[u][i].first , u , d + );
}
} int lca(int u , int v) {
if(dep[u] < dep[v]) {
swap(u , v);
}
for(int k = ; k < ; k++) {
if((dep[u] - dep[v]) >> k & ) {
u = par[u][k];
}
}
if(u == v)
return u;
for(int k = ; k >= ; k--) {
if(par[u][k] != par[v][k]) {
u = par[u][k];
v = par[v][k];
}
}
return par[u][];
} int main()
{
int n , m , q , v , u , d , root , t;
char op[];
scanf("%d" , &t);
while(t--) {
scanf("%d %d" , &n , &m);
init(n);
root = (n + ) * n / ;
for(int i = ; i < n - ; i++) {
scanf("%d %d %d" , &u , &v , &d);
G[u].push_back(P(v , d));
if(!ok[v]) {
root -= v;
ok[v] = ;
}
}
dfs2(root , - , );
dis[root] = ;
for(int k = ; k < ; k++) {
for(int i = ; i <= n ; i++) {
if(par[i][k] <= ) {
par[i][k + ] = ;
}
else {
par[i][k + ] = par[par[i][k]][k];
}
}
}
dfs(root);
for(int i = ; i < m ; i++) {
scanf("%d %d" , &u , &v);
printf("%d\n" , dis[u] + dis[v] - * dis[lca(u , v)]);
}
}
}
树链剖分的LCA：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 5e4 + ;
struct data {
int to , next , cost;
}edge[MAXN << ];
int head[MAXN] , cnt;
int par[MAXN] , dep[MAXN] , top[MAXN] , id[MAXN] , dis[MAXN] , size[MAXN] , son[MAXN]; void init() {
memset(head , - , sizeof(head));
cnt = ;
} inline void add(int u , int v , int cost) {
edge[cnt].to = v;
edge[cnt].next = head[u];
edge[cnt].cost = cost;
head[u] = cnt++;
}
//求size , par , son , dep
void dfs_1(int u , int p , int d) {
par[u] = p , size[u] = , son[u] = u , dep[u] = d;
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p)
continue;
dis[v] = dis[u] + edge[i].cost; //离根的距离
dfs_1(v , u , d + );
if(size[v] > size[son[u]]) //取重儿子
son[u] = v;
size[u] += size[v];
}
}
//求top , id
void dfs_2(int u , int p , int t) { //p为父节点 t为链的祖先
top[u] = t; //链的祖先
id[u] = ++cnt; //点的顺序
if(son[u] != u) //重儿子优先
dfs_2(son[u] , u , t);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == p || v == son[u])
continue;
dfs_2(v , u , v); //树链重新开始
}
}
//树链剖分求lca的复杂度是(nlognlogn)，建议用RMQ求lca
int lca(int u , int v) {
int fu = top[u] , fv = top[v];
while(top[u] != top[v]) { //链是否相同，不同就循环
if(dep[fu] < dep[fv]) { //比较两个链的深度
v = par[fv];
fv = top[fv];
}
else {
u = par[fu];
fu = top[u];
}
}
if(dep[u] >= dep[v]) //在相同的链上
return v;
return u;
} int main()
{
int n , q , u , v , cost , x , y , z , t;
scanf("%d" , &t);
while(t--) {
scanf("%d %d" , &n , &q);
init();
for(int i = ; i < n ; ++i) {
scanf("%d %d %d" , &u , &v , &cost);
add(u , v , cost);
add(v , u , cost);
}
cnt = ;
dfs_1( , , );
dfs_2( , , );
while(q--) {
scanf("%d %d" , &x , &y);
int res = (dis[x] + dis[y] - * dis[lca(x , y)]);
printf("%d\n" , res);
}
}
}