LCA最近公共祖先-- HDU 2586

2019-05-08 07:23:32来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

 

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 by 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 are to 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个节点的树,每条边上有一个权值代表这两个点之间的距离,现在m次询问:从节点a到节点b的路径长?

思路:预处理所有节点到根节点(定为节点1)的距离,以及所有节点的祖先信息(fa[i][j]表示节点 i 向上距离为 (1<<j)的祖先节点编号),计算a和b到根节点的距离和,减去两倍的最近公共祖先的到根节点的距离值。

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 4e4 + 5;

int head[N], cnt;
struct Edge
{
    int to, next;
    int value;
}e[2 * N];

struct Node {
    int fa[20];
    int deep;
    int sum;
    bool state;
}node[N];

void insert(int u, int v, int value)
{
    e[++cnt].to = v;
    e[cnt].next = head[u];
    e[cnt].value = value;
    head[u] = cnt;
    e[++cnt].to = u;
    e[cnt].next = head[v];
    e[cnt].value = value;
    head[v] = cnt;
}
int cal(int x, int t)
{
    for (int i = 0; i <= 19; i++)
        if (t&(1 << i)) x = node[x].fa[i];
    return x;
}
void dfs(int x)
{
    node[x].state = 1;
    for (int i = 1; i <= 19; i++)
    {
        if (node[x].deep<(1 << i))break;
        node[x].fa[i] = node[node[x].fa[i - 1]].fa[i-1];///倍增处理祖先信息
    }
    for (int i = head[x]; i; i = e[i].next)
    {
        if (node[e[i].to].state) continue;
        node[e[i].to].deep = node[x].deep+ 1;
        node[e[i].to].fa[0] = x;
        node[e[i].to].sum = node[x].sum+e[i].value;
        dfs(e[i].to);
    }
}
int lca(int x, int y)///求lca
{
    if (node[x].deep<node[y].deep) swap(x, y);
    x = cal(x, node[x].deep - node[y].deep);
    for (int i = 19; i >= 0; i--)
        if (node[x].fa[i] != node[y].fa[i])
        {
            x = node[x].fa[i];
            y = node[y].fa[i];
        }
    if (x == y)return x;
    else return node[x].fa[0];
}

void init()
{
    cnt = 0;
    memset(head, 0, sizeof(head));
    memset(node, 0, sizeof(node));
}

int main()
{
    int T; cin >> T;
    while (T--)
    {
        init();
        int n, m; cin >> n >> m;
        for (int i = 0; i < n-1; i++) {
            int x, y, v; scanf("%d%d%d",&x,&y,&v);
            insert(x,y,v);
        }
        dfs(1);
        for (int i = 0; i < m; i++) {
            int x, y; scanf("%d%d",&x,&y);
            int pa = lca(x, y);
            int ans = node[x].sum - node[pa].sum + node[y].sum - node[pa].sum;
            cout << ans << endl;
        }
    }
    return 0;
}

 


原文链接:https://www.cnblogs.com/chen9510/p/10809886.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ Primer 回炉重铸(一)

下一篇:Codeforces 1156F Card Bag(概率DP)