原题
思路
先求出最大生成树，然后对每个询问求LCA，求两点走向LCA路径上的最小权值，树剖实现，求最小值懒得写线段树用了RMQ，虽然r<l的情况没特判调了很久。还是比较简单的模板题，但是找了很久bug。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <map>
#include <iostream>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f
#define PI 3.1415926535898
#define F first
#define S second
#define endl '
'
#define lson rt << 1
#define rson rt << 1 | 1
#define lowbit(x) (x & (-x))
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _per(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
const int maxn = 1e5 + 7;
int head[maxn], fat[maxn], p[maxn][30];
int n, m, q;
inline LL read()
{
LL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct pp
{
int fr, v, w;
} edge[maxn];
bool cmp(pp a, pp b)
{
return a.w > b.w;
}
int tot = 0;
void add_e(int u, int v, int w)
{
edge[++tot].fr = u;
edge[tot].w = w;
edge[tot].v = v;
}
inline int fa(int x)
{
return fat[x] == x ? x : fat[x] = fa(fat[x]);
}
inline void unnion(int x, int y)
{
fat[fa(x)] = fa(y);
}
struct node
{
int fr, v, w, nxt;
} e[maxn * 2];
int num = 0;
inline void add(int t1, int t2, int t3)
{
e[++num].fr = t1;
e[num].v = t2;
e[num].w = t3;
e[num].nxt = head[t1];
head[t1] = num;
}
int son[maxn], sz[maxn], f[maxn], dep[maxn];
int w[maxn];
inline void dfs1(int u, int fa)
{
sz[u] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
dep[v] = dep[u] + 1;
f[v] = u;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]])
son[u] = v;
}
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
}
}
int top[maxn], in[maxn];
int cnt = 0;
inline void dfs2(int u, int t)
{
in[u] = ++cnt;
top[u] = t;
if (son[u])
dfs2(son[u], t);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == f[u] || v == son[u])
continue;
dfs2(v, v);
}
}
inline void give_val()
{
_rep(i, 1, num)
{
if (dep[e[i].fr] > dep[e[i].v])
w[in[e[i].fr]] = e[i].w;
else
w[in[e[i].v]] = e[i].w;
}
}
inline void rmq_init()
{
for (int i = 1; i <= cnt; i++)
{
p[i][0] = w[i];
}
for (int j = 1; (1 << j) <= cnt; j++)
{
for (int i = 1; i + (1 << j) - 1 <= cnt; i++)
{
p[i][j] = min(p[i][j - 1], p[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int rmq_min(int l, int r)
{
if (r < l)
return inf;
int k = log2(r - l + 1);
return min(p[l][k], p[r - (1 << k) + 1][k]);
}
inline int LCA(int x, int y)
{
int mn = inf;
int fx = top[x], fy = top[y];
while (fx != fy)
{
if (dep[fx] < dep[fy])
{
swap(x, y);
swap(fx, fy);
}
mn = min(mn, rmq_min(in[fx], in[x]));
x = f[fx], fx = top[x];
}
if (dep[x] < dep[y])
mn = min(mn, rmq_min(in[x] + 1, in[y]));
else
mn = min(mn, rmq_min(in[y] + 1, in[x]));
return mn;
}
int main()
{
n = read(), m = read();
int x, y, v;
_rep(i, 1, m)
{
x = read(), y = read(), v = read();
add_e(x, y, v);
add_e(y, x, v);
}
sort(edge + 1, edge + 1 + tot, cmp);
_rep(i, 1, n) fat[i] = i;
_rep(i, 1, tot)
{
if (fa(edge[i].fr) == fa(edge[i].v))
continue;
unnion(edge[i].fr, edge[i].v);
add(edge[i].fr, edge[i].v, edge[i].w);
add(edge[i].v, edge[i].fr, edge[i].w);
}
_rep(i, 1, n)
{
if (fat[i] != i)
continue;
dfs1(i, i);
dfs2(i, i);
w[in[i]] = inf;
}
give_val();
q = read();
rmq_init();
_rep(i, 1, q)
{
cin >> x >> y;
if (fa(x) != fa(y))
cout << "-1" << endl;
else
cout << LCA(x, y) << endl;
}
}