【HDU No. 2586】 树上距离 How far away ?
杭电 OJ 题目地址
【题意】
有n 栋房屋,由一些双向道路连接起来。
每两栋房屋之间都有一条独特的简单道路(“简单”意味着不可以通过两条道路去一个地方)。人们每天总是喜欢这样问:“我从A房屋到B房屋需要走多远?”
【输入输出】
输入:
第1行是单个整数T (T ≤10),表示测试用例的数量。每个测试用例的第1行都包含n (2≤n ≤40000)和m (1≤m ≤200),表示房屋数量和查询数量。下面的n -1行,每行都包含三个数字i、j、k ,表示有一条道路连接房屋i 和房屋j ,长度为k (0<k≤40000),房屋被标记为1~n 。
接下来的m 行,每行都包含两个不同的整数i 和j ,求房屋i 和房屋j 之间的距离。
输出:
对每个测试用例,都输出m 行查询答案,在每个测试用例后都输出一个空行。
【样例】
【思路分析】
这道题中任意两个房子之间的路径都是唯一的,是连通无环图,属于树形结构,所以求两个房子之间的距离相当于求树中两个节点之间的距离。
可以采用最近公共祖先LCA的方法求解。求解LCA的方法有很多,在此使用树上倍增+ST解决。
【算法设计】
① 根据输入数据采用链式前向星存储图。
② 深度优先搜索,求深度、距离,初始化F[v ][0]。
③ 创建ST。
④ 查询x 、y 的最近公共祖先lca。
⑤ 输出x、y 的距离dist[x ]+dist[y ]-2×dist[lca]。
【举个栗子】
求u 和v 之间的距离,若u 和v 的最近公共祖先为lca,则u 和v之间的距离为u 到树根的距离加上v 到树根的距离,再减去2倍的lca到树根的距离:dist[u ]+dist[v ]-2×dist[lca]。
【算法实现】
#include<iostream>
#include<vector>
#include<algorithm>using namespace std;const int maxn = 40005;int n , m;
int head[maxn] , dis[maxn] , cnt; // 头节点,距离
int fa[maxn] , ans[maxn];bool vis[maxn];
vector<int> query[maxn] , query_id[maxn]; //查询及编号struct Edge{int to , c , next;
}e[maxn << 1];void add(int u , int v , int w){e[++cnt].to = v;e[cnt].c = w;e[cnt].next = head[u];head[u] = cnt;
} void add_query(int x , int y , int id){query[x].push_back(y);query_id[x].push_back(id);query[y].push_back(x);query_id[y].push_back(id);
}int find(int x){ //并查集找祖宗 if(x != fa[x]){fa[x] = find(fa[x]);}return fa[x];
}void tarjan(int u){vis[u] = 1;for(int i = head[u] ; i ; i = e[i].next){int v = e[i].to , w = e[i].c;if(vis[v]){continue;}dis[v] = dis[u] + w;tarjan(v);fa[v] = u;}for(int i = 0 ; i < query[u].size(); i ++){ //u相关的所有查询 int v = query[u][i];int id = query_id[u][i];if(vis[v]){int lca = find(v);ans[id] = dis[u] + dis[v] - 2 * dis[lca];}}
}int main(){int x, y , T , lca;cin >> T;while(T--){cin >> n >> m;for(int i = 1; i <= n ; i++){ // 初始化 head[i] = vis[i] = dis[i] = 0;fa[i] = i;query[i].clear();query_id[i].clear();}cnt = 0;for(int i = 1; i < n; i ++){ //输入一棵树的 n - 1边 int x ,y ,z;cin >> x >> y >> z;add(x , y , z);add(y , x , z);}for(int i = 1; i <= m ; i ++){cin >> x >> y;if(x == y){ans[i] = 0;}else{add_query(x , y , i);}}tarjan(1);for(int i = 1; i<= m ; i++){cout << ans[i] << endl; //输出x 、 y 的距离 }}return 0;
}