26Region_awing

给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：

边是无向的。 所有节点的编号是 1,2,…,n。 输入格式 第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式 共 m 行，对于每次询问，输出一行询问结果。

数据范围 2≤n≤104, 1≤m≤2×104, 0<k≤100, 1≤x,y≤n

输入样例1：
2 2 
1 2 100 
1 2 
2 1
输出样例1：
100
100
输入样例2：
3 2
1 2 10
3 1 15
1 2
3 2
输出样例2：
10
25

题解 Tarjan求最近公共祖先

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168622.html原文链接：https://javaforall.cn