Design the city(LCA + RMQ)

By | 10月09日
Advertisement

Design the city


Time Limit: 1 Second Memory Limit: 32768 KB



Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams everywhere. Now, Cerror finds out that the main reason of them is the poor design of the roads distribution, and he want to change this situation.

In order to achieve this project, he divide the city up to N regions which can be viewed as separate points. He thinks that the best design is the one that connect all region with shortest road, and he is asking you to check some of his designs.

Now, he gives you an acyclic graph representing his road design, you need to find out the shortest path to connect some group of three regions.

Input

The input contains multiple test cases! In each case, the first line contian a interger N (1 < N < 50000), indicating the number of regions, which are indexed from 0 to N-1. In each of the following N-1 lines, there are three interger Ai, Bi, Li (1 < Li < 100) indicating there's a road with length Li between region Ai and region Bi. Then an interger Q (1 < Q < 70000), the number of group of regions you need to check. Then in each of the following Q lines, there are three interger Xi, Yi, Zi, indicating the indices of the three regions to be checked.

Process to the end of file.

Output

Q lines for each test case. In each line output an interger indicating the minimum length of path to connect the three regions.

Output a blank line between each test cases.

Sample Input

4
0 1 1
0 2 1
0 3 1
2
1 2 3
0 1 2
5
0 1 1
0 2 1
1 3 1
1 4 1
2
0 1 2
1 0 3

Sample Output

3
2

2
2

题意:

给出结点数 N ,后给出 N - 1 条边。给出 Q 个询问,每个询问给出 3 个结点,输出这三点连通的最短距离。

思路:

LCA。因为 1 -> 2 + 2 -> 3 的距离等于 1 -> 3 的距离,所以将 3 个点间两两的距离求出后加和除以 2 即为答案。用 LCA 求出两两间点距离即可。输出的格式问题,每个 case 后输出一行空行,最后一组样例不需要有空行。所以用 temp 标记输出即可。

AC:

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int VMAX = 50010;
const int EMAX = VMAX * 2;

int n, ind;
int v[EMAX], fir[VMAX], next[EMAX], w[EMAX];

int cnt;
int vs[VMAX * 2], dep[VMAX * 2], id[VMAX], dis[VMAX];
bool vis[VMAX];

int dp[VMAX * 2][25];

void init () {
    ind = cnt = 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] = cnt;
    vs[cnt] = x;
    dep[cnt++] = 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[cnt] = x;
            dep[cnt++] = d;
        }
    }
}

void RMQ_init () {
    for (int i = 0; i < cnt; ++i) dp[i][0] = i;

    for (int j = 1; (1 << j) <= cnt; ++j) {
        for (int i = 0; i + (1 << j) < cnt; ++i) {
            int a = dp[i][j - 1];
            int b = dp[i + (1 << (j - 1))][j - 1];
            if (dep[a] < dep[b]) dp[i][j] = a;
            else dp[i][j] = b;
        }
    }

}

int RMQ (int L, int R) {
    int len = 0;
    while ((1 << (1 + len)) <= R - L + 1) ++len;
    int a = dp[L][len];
    int b = dp[R - (1 << len) + 1][len];
    if (dep[a] < dep[b]) return a;
    return b;
}

int LCA (int a, int b) {
    int L = min(id[a], id[b]);
    int R = max(id[a], id[b]);
    int node = RMQ(L, R);
    return vs[node];
}

int Distance (int a, int b, int c) {
    int ab = LCA(a, b);
    int ac = LCA(a, c);
    int bc = LCA(b, c);
    int res = 0;
    res += dis[a] + dis[b] - 2 * dis[ab];
    res += dis[a] + dis[c] - 2 * dis[ac];
    res += dis[b] + dis[c] - 2 * dis[bc];
    return res / 2;
}

int main() {

    int temp = 0;

    while (~scanf("%d", &n)) {
        if (temp) printf("\n");

        temp = 1;
        init();

        for (int i = 1; i <= n - 1; ++i) {
            int a, b, val;
            scanf("%d%d%d", &a, &b, &val);
            ++a; ++b;
            add_edge(a, b, val);
            add_edge(b, a, val);
        }

        dis[1] = 0;
        dfs(1, 0);
        RMQ_init();

        int q;
        scanf("%d", &q);
        while (q--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            ++a, ++b, ++c;
            printf("%d\n", Distance(a, b, c));
        }

    }

    return 0;
}

Similar Posts:

  • ZOJ3195 Design the city(LCA)

    题目大概说给一棵树,每次询问三个点,问要把三个点连在一起的最少边权和是多少. 分几种情况..三个点LCA都相同,三个点有两对的LCA是某一点,三个点有两对的LCA各不相同...%--¥-- 画画图可以发现..虽然好像不太严谨..连接(a,b,c)三个点的最短边权和=(dist(a,b)+dist(b,c)+dist(a,c))/2,而dist(u,v)的计算可以预处理出各点到根的距离weight,dist(u,v)=weight(u)+weight(v)-2*weight(lca(u,v))..

  • FZOJ 2014年11月份月赛 ytaaa(dp + RMQ)

    题目链接:http://acm.fzu.edu.cn/contest/problem.php?cid=140&sortid=3 Problem Description Ytaaa作为一名特工执行了无数困难的任务,这一次ytaaa收到命令,需要炸毁敌人的一个工厂,为此ytaaa需要制造一批炸弹以供使用. Ytaaa使用的这种新型炸弹由若干个炸药组成,每个炸药都有它的威力值,而炸弹的威力值为组成这个炸弹的所有炸药的最大威力差的平方,即(max-min)^2,假设一个炸弹有5个炸药组成,威力分别为5

  • hdu 2586 How far away ?(LCA离线)

    记录下所有的提问,在建tarjan建一颗深搜树的时候询问.奇怪这道题的edge开4W会RE,,于是任性的开了40W妥妥过. #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> using namespace std; const int N = 400005; const int M = 205; struct node{ int v, w, nxt; }

  • ANDROID L - Material Design详解(视图和阴影)

    Android L: Google已经确认Android L就是Android Lollipop(5.0). Google之前就已经提前推出了Android L Developer Preview(开发者预览版)来帮助开发者更快的了解Android特性,而不久前也推出了64位的模拟器镜像,而且首次搭载Android L系统的Nexus 6和 Nexus 9也即将上市. 相信Android L正式版离我们也不远了,所以是时候开始学习Android L了! 关于Android L如何配置模拟器和创建

  • How far away ?(LCA 在线算法RMQ)

    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.

  • [POJ]1330 Nearest Common Ancestors (LCA,DFS+ST在线算法 || 倍增算法 || Tarjan离线算法)

    题目链接:http://poj.org/problem?id=1330 题目大意:给定一颗有N个节点的树,给定N-1条边表示父子关系,每次一个询问u, v,求u和v的最近公共祖先 数据范围: 2 <= N <= 10000 题目解答:LCA最近公共祖先的裸题,使用LCA的三种算法均可做 DFS+ST在线算法:(复杂度:O(N*logN+q) ,(查询是O(1)的,q代表查询次数)) #include <cstdio> #include <cstdlib> #includ

  • Nearest Common Ancestors(LCA 离线算法)

    Nearest Common Ancestors Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 18912 Accepted: 10007 Description A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: In the figure, each nod

  • 最大子序列和(dp+ rmq/队列)

    http://exam.upc.edu.cn/problem.php?id=1552 题意:长度为n的数组,再加一限制条件m.求长度最大为m的连续子序列和是多少.m是个正整数 分析:我们都知道如果没有限制条件,求最大连续子序列的和只需用方程:dp[i] = max(0,dp[i - 1] + a[i])即可.复杂度O(n) 此题加上了限制,此时可将dp方程改为:dp[i] =sum[i] - min(sum[i - m + 1] , sum[i - m + 2] , --,sump[i - 1]

  • RMQ算法(ST算法)

    1. 概述 RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值.这两个问题是在实际应用中经常遇到的问题,下面介绍一下解决这两种问题的比较高效的算法.当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN),这里我们暂不介绍. 2.RMQ算法 对于该问题,最容易想到的解决方案是遍历,复杂度是O(n).但当数据量

  • (转)MapReduce Design Patterns(chapter 7 (part 2))(十四)

    External Source Input Pattern Description 这种模式不从hdfs加载数据,而是从hadoop以外系统,例如RDB或web service加载. Intent 想要从非MapReduce框架的系统并行加载数据. Motivation 使用MapReduce分析数据通常的做法是把数据先存储到存储平台上,例如hdfs,然后分析.用这中模式,你可以使用MapReduce框架跟外部系统挂钩,例如数据库或web service,把数据直接拉到mapper. 这里有几个

Tags: