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

LOJ#137. 最小瓶颈路 加强版(Kruskal重构树 rmq求LCA)

程序员文章站 2022-03-25 21:41:45
题意 三倍经验哇咔咔 " 137. 最小瓶颈路 加强版" " 6021. 「from CommonAnts」寻找 LCR" " 136. 最小瓶颈路" Sol 首先可以证明,两点之间边权最大值最小的路径一定是在最小生成树上 考虑到这题是边权的最大值,直接把重构树建出来 然后查LCA处的权值即可 输入 ......

题意

三倍经验哇咔咔

#6021. 「from commonants」寻找 lcr

sol

首先可以证明,两点之间边权最大值最小的路径一定是在最小生成树上

考虑到这题是边权的最大值,直接把重构树建出来

然后查lca处的权值即可

输入文件过大,需要用rmq算法求lca

// luogu-judger-enable-o2
#include<bits/stdc++.h>
const int maxn = 1e6 + 10;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, q, s, tot, dfn[maxn], rev[maxn], dep[maxn], id[maxn][21], lg2[maxn], rd[maxn];
vector<int> v[maxn];
void dfs(int x, int fa) {
    dfn[x] = ++tot; dep[x] = dep[fa] + 1; id[tot][0] = x; 
    for(int i = 0, to; i < v[x].size(); i++) {
        if((to = v[x][i]) == fa) continue;
        dfs(to, x);
        id[++tot][0] = x;
    }
}
void rmq() {
    for(int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1;
    for(int j = 1; j <= 20; j++) {
        for(int i = 1; (i + (1 << j) - 1) <= tot; i++) {
            int r = i + (1 << (j - 1));
            id[i][j] = dep[id[i][j - 1]] < dep[id[r][j - 1]] ? id[i][j - 1] : id[r][j - 1];
        }
    }
}
int query(int l, int r) {
    if(l > r) swap(l, r);
    int k = lg2[r - l + 1];
    return dep[id[l][k]] < dep[id[r - (1 << k) + 1][k]] ? id[l][k] : id[r - (1 << k) + 1][k];
}
int main() {
    freopen("a.in", "r", stdin);
    n = read(); q = read(); s = read();
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    dfs(s, 0);
    rmq();
    while(q--) {
        int x = read(), y = read();
        printf("%d\n", query(dfn[x], dfn[y]));
    }
    return 0;
}