LCA最近公共祖先-- HDU 2586

「爱情、让人受尽委屈。」 2021-12-01 17:34 245阅读 0赞

[题目链接][Link 1]

**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**

3 2

1 2 10

3 1 15

1 2

2 3

2 2

1 2 100

1 2

2 1

**Sample Output**

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

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2586