正文
LCA - 求任意两点间的距离
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
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.
InputFirst 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.OutputFor each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.Sample Input
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.OutputFor 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 32 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100题目分析 ： 给出一些点之间的长度，再给出一些询问，查任意两点间的距离。
思路分析 ： 倍增LCA裸题
代码示例 ：
#define ll long long
const int maxn = 4e4+5;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;int n, m, N;
struct node
{
int to, cost;
node(int _to = 0, int _cost = 0):to(_to),cost(_cost){}
};
vector<node>ve[maxn];
int dep[maxn];
int grand[maxn][30], gw[maxn][30];void dfs(int x, int fa){
for(int i = 1; i <= N; i++){
grand[x][i] = grand[grand[x][i-1]][i-1];
gw[x][i] = gw[x][i-1] + gw[grand[x][i-1]][i-1];
}
for(int i = 0; i < ve[x].size(); i++){
int to = ve[x][i].to;
int cost = ve[x][i].cost; if (to == fa) continue;
dep[to] = dep[x] + 1;
grand[to][0] = x;
gw[to][0] = cost;
dfs(to, x);
}
}int lca(int a, int b){
// a 是在 b 的上面的
if (dep[a] > dep[b]) swap(a, b);
int ans = 0; for(int i = N; i >= 0; i--){
if (dep[a] < dep[b] && dep[grand[b][i]] >= dep[a]){
ans += gw[b][i];
b = grand[b][i];
}
}
// a, b 在同一层后
for(int i = N; i >= 0; i--){
if (grand[a][i] != grand[b][i]) {
ans += gw[a][i];
ans += gw[b][i];
a = grand[a][i], b = grand[b][i];
}
}
if (a != b) {
ans += gw[a][0];
ans += gw[b][0];
}
return ans;
}int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int t;
int a, b, c; cin >> t;
while(t--){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) ve[i].clear();
for(int i = 1; i < n; i++){
scanf("%d%d%d", &a, &b, &c);
ve[a].push_back(node(b, c));
ve[b].push_back(node(a, c));
}
memset(grand, 0, sizeof(grand));
memset(gw, 0, sizeof(gw));
dep[1] = 0;
N = floor(log(n)/log(2)); // 求出最大的2^k = N中的 k
dfs(1, 1);
for(int i = 1; i <= m; i++){
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
}
return 0;
}/*
5
8 100
1 2 1
2 4 1
2 5 1
2 6 1
1 3 1
3 7 1
1 8 1
*/
