题意：
给出一个有n(<=1e5)个点，m(<=5e5)条无向边的图，然后有q个询问（<=1e5），每次询问两个点u，v，询问他们之间两条及其以上没有重复边的路径，如果有，那么就选出两条路径使得组成这两条路径的边的最大值最小。
题解：
因为要求两条路径使得边的最大值最小，那么可以首先保证的是一条路径的边最小，那么就可以考虑先求一棵最小生成树以保证一条路径最小。
那么现在考虑将非树边的边从小到大加入生成树中，那么必定会在这条边的两个端点的LCA处形成一个环，环中的任意两点都会有两条路径，又因为是从小到大加入的，那么当前必定为最优解。更新环中的所有的点的值，更新过的不再更新。
对于询问u, v那么可以倍增到LCA，求路径最大值就好啦~
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int INF = (1 << 31) - 1;
int dep[N], anc[20][N], maxi[20][N], w[N], vis[N], n, m, q, pa[N];
struct edge {int u, v;} E[N];
vector <int> e[N];
int find (int x)
{
return x == pa[x] ? x : pa[x] = find (pa[x]);
}
bool cmp (edge a, edge b)
{
return abs(w[a.u] - w[a.v]) < abs(w[b.u] - w[b.v]);
}
void Dfs (int u, int pre)
{
anc[0][u] = pre, dep[u] = dep[pre] + 1;
for (int i = 0; i < e[u].size(); ++i)
{
int v = e[u][i];
if (v != pre) Dfs (v, u);
}
}
void getans(int u, int v)
{
int d = 0;
if (dep[u] < dep[v]) swap (u, v);
for (int i = 18; i >= 0; --i)
{
if (dep[anc[i][u]] >= dep[v])
{
d = max (d, maxi[i][u]);
u = anc[i][u];
}
}
while (u != v)
{
for (int i = 18; i >= 0; --i)
{
if (anc[i][u] == anc[i][v] && i) continue;
d = max (d, max (maxi[i][u], maxi[i][v]));
u = anc[i][u], v = anc[i][v];
}
}
if (d == INF) puts("infinitely");
else printf ("%d
", d);
}
int main ()
{
scanf ("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i) scanf ("%d", &w[i]);
for (int i = 1; i <= m; ++i)
scanf ("%d%d", &E[i].u, &E[i].v);
sort (E + 1, E + 1 + m, cmp);
for (int i = 1; i <= n; ++i) pa[i] = i;
for (int i = 1; i <= m; ++i)
{
int u = find (E[i].u), v = find (E[i].v);
if (u != v)
{
vis[i] = 1;
pa[u] = v;
e[E[i].u].push_back(E[i].v);
e[E[i].v].push_back(E[i].u);
}
}
Dfs (1, 0);
for (int i = 1; i <= n; ++i) pa[i] = i, maxi[0][i] = INF;
for (int i = 1; i <= m; ++i)
{
if (vis[i]) continue;
int u = find (E[i].u), v = find (E[i].v);
while (u != v)
{
if (dep[u] < dep[v]) swap(u, v);
maxi[0][u] = abs (w[E[i].u] - w[E[i].v]);
pa[u] = anc[0][u];
u = find(u);
}
}
for (int i = 1; i <= 18; ++i)
{
for (int j = 1; j <= n; ++j)
{
anc[i][j] = anc[i - 1][anc[i - 1][j]];
maxi[i][j] = max (maxi[i - 1][j], maxi[i - 1][anc[i - 1][j]]);
}
}
for (int i = 1; i <= q; ++i)
{
int u, v;
scanf ("%d%d", &u, &v);
getans(u, v);
}
return 0;;
}
总结：
既然要求两条路，那么首先需要保证第一条路QAQ