模板倍增LCA 求树上两点距离 hdu2586

时间：2023-03-09 02:22:21
模板倍增LCA 求树上两点距离 hdu2586

http://acm.hdu.edu.cn/showproblem.php?pid=2586

课上给的ppt里的模板是错的，wa了一下午orz。最近总是被坑啊。。。

题解：树上两点距离转化为到根的距离之和减去重复部分，相当于前缀和

dis[x] + dis[y] - 2ll * dis[LCA(x, y)]
#define _CRT_SECURE_NO_WARNINGS

#include<cmath>

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<stack>

#include<vector>

#include<string.h>

using namespace std;

#define rep(i,t,n)  for(int i =(t);i<=(n);++i)

#define per(i,n,t)  for(int i =(n);i>=(t);--i)

#define mmm(a,b) memset(a,b,sizeof(a))

#define eps 1e-6

#define pb push_back

typedef long long ll;

stack <int> dl;

const int maxn=1e5+;

int f[maxn][];

int fa[maxn];

ll dis[maxn];

int dep[maxn];

int n, m;

 vector<pair<int,ll> > E[maxn];

 void dfs(int rt,int p) {

     for (int i = ; i < E[rt].size(); i++) {

         pair<int,int> v = E[rt][i];

         if (v.first == p)continue;

         fa[v.first] =rt ;

         dep[v.first] =dep[rt]+ ;

         dis[v.first] = dis[rt] + v.second;

         dfs(v.first, rt);

     }

 }

void Init_LCA() {

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

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

            f[i][j] = -;

    for (int i = ; i <= n; ++i) f[i][] = fa[i];

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

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

            if (f[i][j - ] != -)

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

}

int LCA(int x, int y) {

    if (dep[x] < dep[y]) swap(x, y);

    int i, lg;

    for (lg = ; ( << lg) <= dep[x]; ++lg);

    --lg;

    /// 使x往上走直到和y在同一水平线上；

    for (i = lg; i >= ; --i)

        if (dep[x] - ( << i) >= dep[y])

            x = f[x][i];

    if (x == y) return x;

    /// 此时x，y在同一水平线上，使x，y同时以相同的速度(2^j)往上走；

    for (i = lg; i >= ; --i)

        if (f[x][i] != - && f[x][i] != f[y][i])

            x = f[x][i], y = f[y][i];

    return fa[x];

}

int main()

{

    int t;

    cin >> t;

    while (t--) {

        cin >> n >> m;

        rep(i, , n)E[i].clear();

        //mmm(dis, 0); mmm(fa, 0); mmm(f, 0); mmm(dep, 0);

        rep(i, , n-) {

            int x, y;

            ll z;

            scanf("%d%d%lld", &x, &y, &z);

            //f[x][0] = y;

            E[x].push_back(make_pair(y,z));

            E[y].push_back(make_pair(x,z));

        }

        dis[] = ;

        //fa[1] = 1;

        //dep[1] = 0;

        dfs(, -);

        Init_LCA();

        rep(i, , m) {

            int x, y;

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

            printf("%lld\n", dis[x] + dis[y] - 2ll * dis[LCA(x, y)]);

        }

        //cout << endl;

    }

    cin >> n;

    return ;

}/*

 2

5 2

1 2 10

2 3 10

3 4 10

4  5 10

1 5

5 3

 */

相关文章