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. |
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. |
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
题目大意：村子里有n栋房子，还有一些双向的道路把它们连接起来。每天人们总是喜欢这样问:“如果我想从A家到B家有多远?”通常很难回答。但幸运的是，在这个村子里，答案总是独一无二的，因为道路的建造方式是：每两栋房子之间有一条独特的简单道路。你的任务是回答所有这些好奇的人。
这是一道LCA的入门题 今天第一次接触 先用了倍增的方法解出了这道题（主要还是有参考的成分
大佬讲这种题很简单的。。。但是我还是感觉好难
第一次写题解。。。简单分析下思路 主要还是看注释8
[cpp]
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<string>
#include<queue>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int eps = 1e-7;
const int maxn =4e4+5;
const int maxbit = 15;
const double PI = 3.14;
struct edge{
int to;//边指向哪里
int val;//这条边的权值（长度
};
int father[maxn][maxbit];//father数组 存一个节点向上爬完之后的节点
int dep[maxn];//每个节点的深度
int dis[maxn];//从根节点到各个节点的深度
vector<edge> G[maxn];//存图
int lg[maxn];//log数组
void dfs(int nowp, int fa) {//dfs确定每个节点的深度
dep[nowp] = dep[fa] + 1;//当前节点的深度等于父节点深度加一
father[nowp][0] = fa;//当前节点向上爬一次这里注意2的0次方是第一次 2的1次方是第二次 以此类推 因此 当前节点向上爬一次为父节点
for (int j = 1; j <= lg[dep[nowp]] + 1; j++) {//向上爬2的j次方次相当于先爬2的j-1次方再爬2的j-1次方次
father[nowp][j] = father[father[nowp][j - 1]][j - 1];
}
for (int i = 0; i < G[nowp].size(); i++) {//之后开始遍历这个点连接到的所有边
edge& e = G[nowp][i];//复制当前边
if (e.to != fa) {//如果这条边所到达的地方不是父节点
dis[e.to] = dis[nowp] + e.val;//更新dis数组 长度增加
dfs(e.to, nowp);//深搜
}
}
}
int lca(int u, int v) {//lca算法
if (dep[u] < dep[v])//首先确定 u>v
swap(u, v);
while (dep[u] != dep[v])//如果u的深度大于v 那么向上爬log2[u和为v的深度差] 直到深度相等 注意是深度
u = father[u][lg[dep[u] - dep[v]]];
if (u == v)//如果这两个节点相等 那么直接返回
return u;
for (int j = lg[dep[u]]; j >= 0; j--) {//如果u和v只是深度相等 本质并不相等 那么进行下列步骤
if (father[u][j] != father[v][j]) {//如果u向上爬2的j次方不等于v向上爬2的j次方 u和v分别找到2的j次方之后的节点
u = father[u][j];
v = father[v][j];
}
}
return father[u][0];//返回两个不相等节点的父节点(此时u v 为兄弟节点
}
int main() {
ios::sync_with_stdio(0);
lg[0] = -1;//log2n 取整
for (int i = 1; i < maxn; i++) {
lg[i] = lg[i >> 1] + 1;
}
int t;
cin >> t;
while (t--) {
memset(father, 0, sizeof(father));
memset(dep, 0, sizeof(dep));
memset(dis, 0, sizeof(dis));
for (int i = 0; i < maxn; i++) {
G[i].clear();
}
int n, m;
cin >> n >> m;
int x, y, k;
for (int i = 1; i <= n - 1; i++) {//建图
cin >> x >> y >> k;
G[x].push_back({ y,k });
G[y].push_back({ x,k });
}
dfs(1, 0);//从顶部开始搜
while (m--) {
cin >> x >> y;
int LCA = lca(x, y);
cout << dis[x] - dis[LCA] + dis[y] - dis[LCA] << endl;
}
}
return 0;
}
[/cpp]
Comments | NOTHING