弱弱地问一句

for (int i = 1; i <= n; i ++) {
	if (tag[fid(i)]) continue;
	tag[fid(i)] = true;
	add(0, i, 0);
}
deep[n + 1] = -1;
g[0][0] = inf;
f[0][0] = n + 1;
dfs (0, n + 1);

for (int i = 1; i <= n; i ++) {
	if (tag[fid(i)]) continue;
	tag[fid(i)] = true;
	dfs (i, 0);
}

上面的两段不同的代码（上面是pts80的，下面是AC的），大概都是想处理：弄完最大生成树后，在图不为连通图（即分成了多个树）的情况

以下是完整的代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, maxm = 3e5 + 5;
int n, m, q;
#define inf 0x3f3f3f3f
struct Point {
	int u, v, w;
	Point (int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
	friend bool operator < (Point e1, Point e2) {
		return e1.w > e2.w;  //边的升序排列
	}
} pp[maxm];    //所有边都存在这里
struct Edge {
	int nex, v, w;
	Edge (int a = 0, int b = 0, int c = 0) : nex(a), v(b), w(c) {}
} edge[maxm << 1];  //被用来建树的边
int cnt, head[maxn];   //链式前向星
void add (int u, int v, int w) {
	edge[cnt] = Edge(head[u], v, w);
	head[u] = cnt ++;
}
int root[maxn];
int fid (int x) {return x == root[x] ? x : root[x] = fid(root[x]);}
bool Merge (int x, int y) {
	int fx = fid(x), fy = fid(y);
	if (!(fx ^ fy)) return false;
	root[fx] = fy;
	return true;
}
bool same(int u, int v) {return fid(u) == fid(v);}
//以上是并查集
int deep[maxn], Log2[maxn]；
int f[maxn][20];   //向上倍增数组
int g[maxn][20];   //向上倍增这段区间的最短边
void dfs (int u, int fa) {   //dfs处理信息
	deep[u] = deep[fa] + 1;
	for (int k = 1; k <= Log2[deep[u]]; k ++) {
		f[u][k] = f[f[u][k - 1]][k - 1];
		g[u][k] = min(g[u][k - 1], g[f[u][k - 1]][k - 1]);
	}
	for (int i = head[u], v, w; ~i; i = edge[i].nex) {
		v = edge[i].v;
		if (!(v ^ fa)) continue;
		w = edge[i].w;
		f[v][0] = u;
		g[v][0] = w;
		dfs (v, u);
	}
}
int query (int u, int v) {   //倍增LCA查找答案
	if (deep[u] < deep[v]) swap(u, v);
	int tmp = deep[u] - deep[v];
	int ans = inf;
	for (int i = Log2[tmp]; i >= 0; i --) {
		if ((tmp >> i) & 1) {
			ans = min(ans, g[u][i]);
			u = f[u][i];
		}
	}
	if (!(u ^ v)) return ans;
	for (int i = Log2[deep[u]]; i >= 0; i --) {
		if (f[u][i] ^ f[v][i]) {
			ans = min(ans, min(g[u][i], g[v][i]));
			u = f[u][i];
			v = f[v][i];
		}
	}
	ans = min(ans, min(g[u][0], g[v][0]));
	return ans;
}
bool tag[maxn];
void init () {
	cnt = 0;
	for (int i = 1; i <= n; i ++) {
		head[i] = -1;
		root[i] = i;
		for (int k = 0; k <= Log2[n]; k ++) {
			g[i][k] = inf;
		}
	}
	for (int i = 2; i <= n; i ++) {
		Log2[i] = Log2[i >> 1] + 1;
	}
}
int main () {
	scanf ("%d%d%d", &n, &m, &q);
	init ();
	for (int i = 1, u, v, w; i <= m; i ++) {
		scanf ("%d%d%d", &u, &v, &w);
		pp[i] = Point(u, v, w);
	}
	sort (pp + 1, pp + m + 1);
	for (int i = 1, u, v, w; i <= m; i ++) {
		u = pp[i].u, v = pp[i].v;
		if (Merge (u, v)) {
			w = pp[i].w;
			add(u, v, w);
			add(v, u, w);
		}
	}
//-------------------------------------------
//  这下面两个循环有什么区别??? 
//  为什么换成这个被注释了的东西就 WA on #9 #10 ???  
//	for (int i = 1; i <= n; i ++) {
//		if (tag[fid(i)]) continue;
//		tag[fid(i)] = true;
//		add(0, i, 0);
//	}
//	deep[n + 1] = -1;
//	g[0][0] = inf;
//	f[0][0] = n + 1;
//	dfs (0, n + 1);
//-------------------------------------------
	for (int i = 1; i <= n; i ++) {
		if (tag[fid(i)]) continue;
		tag[fid(i)] = true;
		dfs (i, 0);
	}
//-------------------------------------------
	for (int i = 1, x, y; i <= q; i ++) {
		scanf ("%d%d", &x, &y);
		if (!same(x, y)) printf ("-1\n");
		else printf ("%d\n", query(x, y));
	}
	return 0;
}