题目描述
给出 n 个点的一棵树(n-1条边的连通图),多次询问两点之间的最短距离。
输入格式
第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;
下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k;
再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行,对于每次询问,输出一行询问结果。
直接套最近公共祖先模板+dp
我们可以令cnt[i][j]表示在第i个节点向上走2^j次方步所走的长度,所以有状态转移方程:
cnt[i][j] = cnt[i][j-1] + cnt[fa[i][j-1]][j-1]
所有状态转移方程可以直接放到fa[i][j]过程当中一起实现,其他的直接套公共祖先模板就可以了。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 20010, INF = 0x3f3f3f3f, T=20;
int e[N], ne[N], h[N], w[N], idx;
int depth[N], fa[N][T], cnt[N][T];
//cnt[i][j]表示在第i个节点向上走2^j次方步所走的长度,所以有状态转移方程:cnt[i][j] = cnt[i][j-1] + cnt[fa[i][j-1]][j-1]
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
void bfs(){
memset(depth, 0x3f3f3f3f, sizeof depth);
depth[0] = 0;
depth[1] = 1;
queue<int> qu;
qu.push(1);
while(qu.size()){
int val = qu.front();
qu.pop();
for (int i = h[val]; i != -1; i = ne[i]) {
int k = e[i];
if (depth[k] > depth[val] + 1){
depth[k] = depth[val] + 1;
qu.push(k);
fa[k][0] = val;
cnt[k][0] = w[i];
for (int j = 1; j < T; j ++) {
cnt[k][j] = cnt[k][j-1] + cnt[fa[k][j-1]][j-1];
fa[k][j] = fa[fa[k][j-1]][j-1];
}
}
}
}
}
int query(int x, int y){
int ans = 0;
if (depth[x] < depth[y]) swap(x, y);
for (int i = T-1; i >= 0; i --) {
if (depth[fa[x][i]] >= depth[y]) {
ans += cnt[x][i];
x = fa[x][i];
}
}
if (x == y) return ans;
for (int i = T-1; i >= 0; i --) {
if (fa[x][i] != fa[y][i]) {
ans += cnt[x][i] + cnt[y][i];
x = fa[x][i];
y = fa[y][i];
}
}
ans += cnt[x][0] + cnt[y][0];
return ans;
}
int main(){
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i =1; i < n; i ++) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
add(x, y, k);
add(y, x, k);
}
bfs();
while(m --) {
int x, y;
scanf("%d%d", &x, &y);
int ans = query(x, y);
printf("%d\n", ans);
}
return 0;
}