题目描述 Description

小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力

输入描述 Input Description

第一行一个n，接下来n-1行每一行有三个整数u, v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。

第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u, v 表示两只虫子所在的节点

输出描述 Output Description

一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。

样例输入 Sample Input

3

1 0 1

2 0 1

3

1 0

2 0

1 2

样例输出 Sample Output

1

1

2

数据范围及提示 Data Size & Hint

1<=n<=50000，1<=m<=75000，0<=c<=1000

题解和代码

这道题显然是一道LCA的题目，我们可以跑一遍树上倍增。

#include <iostream>

#include <deque>

#include <vector>

#include <cmath>

using namespace std;

int n, m;

struct edge_type

{

    int u, v, c, nextu, nextv;

};

edge_type edge[50005];

const int root = 0;

int hu[50005], hv[50005], fa[50005], fac[50005], deep[50005], f[50005][30], maxdeep = 0, fsum[50005][30];

int maxi;

bool vis[50005];

vector<int> son[50005];

deque<int> q;

void bfs_build_tree(const int root)

{

    q.push_back(root);

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

    {

        vis[i] = false;

    }

    vis[root] = true;

    deep[root] = 1;

    int now;

    while (!q.empty())

    {

        now = q.front();

        if (maxdeep < deep[now])

            maxdeep = deep[now];

        q.pop_front();

        int i = hu[now];

        while (i)

        {

            if (!vis[edge[i].v])

            {

                q.push_back(edge[i].v);

                vis[edge[i].v] = true;

                fa[edge[i].v] = now;

                fac[edge[i].v] = edge[i].c;

                son[now].push_back(edge[i].v);

                deep[edge[i].v] = deep[now] + 1;

            }

            i = edge[i].nextu;

        }

        i = hv[now];

        while (i)

        {

            if (!vis[edge[i].u])

            {

                q.push_back(edge[i].u);

                vis[edge[i].u] = true;

                fa[edge[i].u] = now;

                fac[edge[i].u] = edge[i].c;

                son[now].push_back(edge[i].u);

                deep[edge[i].u] = deep[now] + 1;

            }

            i = edge[i].nextv;

        }

    }

}

void get_f()

{

    maxi = log2(double(maxdeep)-0.5);

    for (int j = 0; j < n; ++j)

    {

        f[j][0] = fa[j];

        fsum[j][0] = fac[j];

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

            fsum[j][i] = f[j][i] = -1;

    }

    fsum[0][0] = f[0][0] = -1;

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

        for (int j = 1; j < n; ++j)

            if ((1 << i) < deep[j])

            {

                f[j][i] = f[f[j][i-1]][i-1];

                fsum[j][i] = fsum[j][i-1] + fsum[f[j][i-1]][i-1];

            }

}

int g(int x, int y)

{

    int ret = 0, a = x, b = y;

    while (deep[b] > deep[a])

    {

        for (int i = maxi; i >= 0; --i)

            if (deep[f[b][i]] > deep[a])

            {

                ret += fsum[b][i];

                b = f[b][i];

            }

        if (deep[fa[b]] == deep[a])

        {

            ret += fac[b];

            b = fa[b];

        }

    }

    while (deep[a] > deep[b])

    {

        for (int i = maxi; i >= 0; --i)

            if (deep[f[a][i]] > deep[b])

            {

                ret += fsum[a][i];

                a = f[a][i];

            }

        if (deep[fa[a]] == deep[b])

        {

            ret += fac[a];

            a = fa[a];

        }

    }

    while (a != b)

    {

        for (int i = maxi; i >= 0; --i)

            if (f[a][i] != f[b][i])

            {

                ret += (fsum[a][i] + fsum[b][i]);

                a = f[a][i];

                b = f[b][i];

            }

        if (fa[a] == fa[b])

        {

            ret += (fac[a] + fac[b]);

            a = fa[a];

            b = fa[b];

        }

    }

    return ret;

}

int main()

{

    cin >> n;

    int u, v, c;

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

    {

        cin >> u >> v >> c;

        edge[i].u = u;

        edge[i].v = v;

        edge[i].c = c;

        edge[i].nextu = hu[u];

        edge[i].nextv = hv[v];

        hu[u] = i;

        hv[v] = i;

    }

    bfs_build_tree(root);

    get_f();

    cin >> m;

    int a, b;

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

    {

        cin >> a >> b;

        cout << g(a, b) << endl;

    }

}