LCA最近公共祖先-- HDU 2586

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 + ;

int head[N], cnt;

struct Edge

{

    int to, next;

    int value;

}e[ * N];

struct Node {

    int fa[];

    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 = ; i <= ; i++)

        if (t&( << i)) x = node[x].fa[i];

    return x;

}

void dfs(int x)

{

    node[x].state = ;

    for (int i = ; i <= ; i++)

    {

        if (node[x].deep<( << i))break;

        node[x].fa[i] = node[node[x].fa[i - ]].fa[i-];///倍增处理祖先信息

    }

    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+ ;

        node[e[i].to].fa[] = 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 = ; i >= ; 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[];

}

void init()

{

    cnt = ;

    memset(head, , sizeof(head));

    memset(node, , sizeof(node));

}

int main()

{

    int T; cin >> T;

    while (T--)

    {

        init();

        int n, m; cin >> n >> m;

        for (int i = ; i < n-; i++) {

            int x, y, v; scanf("%d%d%d",&x,&y,&v);

            insert(x,y,v);

        }

        dfs();

        for (int i = ; 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 ;

}

巴特西

LCA最近公共祖先-- HDU 2586

最新文章

热门文章