欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj1986 Distance Queries(lca又是一道模版题)

程序员文章站 2022-05-27 16:15:17
...

题目链接:http://poj.org/problem?id=1986

题意:就是老问题求val[u]+val[v]-2*val[root]就行。还有这题没有给出不联通怎么输出那么题目给出的数据一定

是联通的。

 

题解:就是单纯的lca。

 

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int M = 8e4 + 10;
vector<pair<int , int> >vc[M];
int p[M][20] , val[M] , deep[M];
void dfs(int pos , int pre , int d) {
    p[pos][0] = pre;
    deep[pos] = d;
    int len = vc[pos].size();
    for(int i = 0 ; i < len ; i++) {
        int u = vc[pos][i].first;
        if(u != pre) {
            val[u] += val[pos] + vc[pos][i].second;
            dfs(u , pos , d + 1);
        }
    }
}
void init(int n) {
    for(int i = 0 ; i < 18 ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            if(p[j][i] == -1) {
                p[j][i + 1] = -1;
            }
            else {
                p[j][i + 1] = p[p[j][i]][i];
            }
        }
    }
}
int lca(int a , int b) {
    if(deep[a] < deep[b]) {
        swap(a , b);
    }
    int d = deep[a] - deep[b];
    for(int i = 0 ; i < 18 ; i++) {
        if(d & (1 << i)) {
            a = p[a][i];
        }
    }
    if(a == b) {
        return a;
    }
    for(int i = 17 ; i >= 0 ; i--) {
        if(p[a][i] != p[b][i] && p[a][i] != -1) {
            a = p[a][i];
            b = p[b][i];
        }
    }
    return p[a][0];
}
int main() {
    int n , m , u , v , w , k;
    char cp[10];
    while(scanf("%d%d" , &n , &m) != EOF) {
        for(int i = 1 ; i <= n ; i++) {
            val[i] = 0;
            vc[i].clear();
        }
        for(int i = 1 ; i < n ; i++) {
            scanf("%d%d%d%s" , &u , &v , &w , cp);
            vc[u].push_back(make_pair(v , w));
            vc[v].push_back(make_pair(u , w));
        }
        memset(p , -1 , sizeof(p));
        dfs(1 , -1 , 1);
        init(n);
        scanf("%d" , &k);
        while(k--) {
            scanf("%d%d" , &u , &v);
            printf("%d\n" , val[u] + val[v] - 2 * val[lca(u , v)]);
        }
    }
    return 0;
}