How far away ?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5810 Accepted Submission(s): 2182
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.
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
题意:
给出 T(0 ~ 10) 组 case,每个 case 给出 N(2 ~ 40000) 个节点和 M (1 ~ 200)个询问,后给出 N - 1 条边的两节点和权值。每次询问输出一个答案,输出 a 到 b 的距离。
思路:
LCA。RMQ 的在线算法,任何一个根为起点都可以,dfs 的时候顺便用 dis 记录到根的距离,求出 a 和 b 的 LCA c,则距离等于 dis [ a ] + dis [ b ] - 2 X dis [ c ]。因为 RMQ 数组的长度开小了,所以 WA 了很多遍。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int VMAX = 40010; const int EMAX = VMAX * 10; int n, ind; int next[EMAX], fir[VMAX], w[EMAX], v[EMAX]; int k; int dis[VMAX], vs[VMAX * 5], dep[VMAX * 5], id[VMAX]; bool vis[VMAX]; int dp[VMAX * 5][25]; void init () { ind = k = 0; memset(fir, -1, sizeof(fir)); memset(vis, 0, sizeof(vis)); } void add_edge (int f, int t, int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ++ind; } void dfs (int x, int d) { id[x] = k; vs[k] = x; dep[k++] = d; vis[x] = 1; for (int e = fir[x]; e != -1; e = next[e]) { int V = v[e]; if (!vis[V]) { dis[V] = dis[x] + w[e]; dfs(V, d + 1); vs[k] = x; dep[k++] = d; } } } void RMQ_init () { for (int i = 0; i < k; ++i) dp[i][0] = i; for (int j = 1; (1 << j) <= k; ++j) { for (int i = 0; i + (1 << j) - 1 < k; ++i) { int a = dp[i][j - 1]; int b = dp[i + (1 << (j - 1))][j - 1]; if (dep[a] > dep[b]) dp[i][j] = b; else dp[i][j] = a; } } } int RMQ (int L, int R) { int len = 0; while ((1 << (len + 1)) <= (R - L + 1)) ++len; int a = dp[L][len]; int b = dp[R - (1 << len) + 1][len]; if (dep[a] > dep[b]) return b; return a; } int LCA (int a, int b) { int L = min(id[a], id[b]); int R = max(id[a], id[b]); int Min = RMQ(L, R); return vs[Min]; } int main () { int T; scanf("%d", &T); while (T--) { init(); int m; scanf("%d%d", &n, &m); for (int i = 1; i <= n - 1; ++i) { int a, b, val; scanf("%d%d%d", &a, &b, &val); add_edge(a, b, val); add_edge(b, a, val); } dfs (1, 1); RMQ_init(); while (m--) { int a, b; scanf("%d%d", &a, &b); int node = LCA(a, b); printf("%d\n", dis[a] + dis[b] - 2 * dis[node]); } } return 0; }
相关推荐
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
算法学习
很详细的LCA与RMQ计算过程的图例演示,以及他们之间的转换
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
1、 概述LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
a very good presentation, ideal for quick learning of some LCA and RMQ aproaches
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
算法合集之RMQ与LCA问题PPT学习教案.pptx
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
3.郭华阳《RMQ与LCA问题》.ppt
原文来自于http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor。 翻译成中文。 LCA RMQ
ACM中的RMQ和LCA问题 对一个区间的最小值询问,也可以是最大值
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)