[LCA]HDU-2586

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

10
25
100
100

题目大意：村子里有n栋房子，还有一些双向的道路把它们连接起来。每天人们总是喜欢这样问:“如果我想从A家到B家有多远?”通常很难回答。但幸运的是，在这个村子里，答案总是独一无二的，因为道路的建造方式是：每两栋房子之间有一条独特的简单道路。你的任务是回答所有这些好奇的人。

这是一道LCA的入门题 今天第一次接触 先用了倍增的方法解出了这道题（主要还是有参考的成分
大佬讲这种题很简单的。。。但是我还是感觉好难
第一次写题解。。。简单分析下思路 主要还是看注释8

[cpp] #include #include #include #include #include #include #include #include #include #include #include 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 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]

uncategorized > HDU
[LCA]HDU-2586
https://47.97.0.163/2019/04/16/lcahdu-2586/
作者
John Doe
发布于
2019年4月16日
许可协议