題目鏈接

題目難度

洛谷上是藍題，我覺得這道題挺簡單的，一眼就看穿了，應該是綠題。

題目解法概括

kruskal 重構樹 + 倍增優化求路徑最大邊權。

代碼

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e5 + 5;
const LL Maxm = 3 * 1e5 + 5;
const LL Maxk = 20;
const LL Inf = 1e18;struct node {LL a, b, e;
} Edge[Maxm];struct node2 {LL to, e;
};
vector<node2> tree[Maxn];LL bfa[Maxn], father[Maxn][Maxk], depth[Maxn], maxDis[Maxn][Maxk];
bool vis[Maxn];void init_bfa(LL n) {for (LL i = 0; i <= n; ++i)  bfa[i] = i;return;
}LL f_find(LL x) {if (x == bfa[x])  return x;else  return bfa[x] = f_find(bfa[x]);
}bool f_join(LL u, LL v) {u = f_find(u);v = f_find(v);if (u == v)  return false;bfa[v] = u;return true;
}void dfs(LL u, LL fa) {vis[u] = true;depth[u] = depth[fa] + 1;father[u][0] = fa;for (LL i = 1; depth[u] > (1 << i); ++i) {father[u][i] = father[father[u][i - 1]][i - 1];maxDis[u][i] = max(maxDis[u][i - 1], maxDis[father[u][i - 1]][i - 1]);}for (auto elem : tree[u]) {if (elem.to == fa)  continue;maxDis[elem.to][0] = elem.e;dfs(elem.to, u);}return;
}LL path_num(LL u, LL v) {if (depth[u] < depth[v])  swap(u, v);LL res = -Inf;for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v]) {res = max(res, maxDis[u][i]);u = father[u][i];}}if (u == v)  return res;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {res = max(res, max(maxDis[u][i], maxDis[v][i]));u = father[u][i];v = father[v][i];}}if (father[u][0] == 0)  return -Inf;else {res = max(res, max(maxDis[u][0], maxDis[v][0]));return res;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, q, s, t;cin >> n >> m;for (LL i = 1; i <= m; ++i) {cin >> Edge[i].a >> Edge[i].b >> Edge[i].e;}sort(Edge + 1, Edge + m + 1, [](const node& x, const node& y) {return x.e < y.e;});init_bfa(n);for (LL i = 1; i <= m; ++i) {if (f_join(Edge[i].a, Edge[i].b) != false) {tree[Edge[i].a].push_back({Edge[i].b, Edge[i].e});tree[Edge[i].b].push_back({Edge[i].a, Edge[i].e});}}for (LL i = 1; i <= n; ++i) {if (vis[i] == false)  dfs(i, 0);}cin >> q;LL res = 0;while (q--) {cin >> s >> t;res = path_num(s, t);if (res == -Inf)  cout << "impossible" << '\n';else  cout << res << '\n';}return 0;
}

（此題和P1967差不多，詳細見這篇博客）