BZOJ 3732 Network

#include<bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&& ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=30000+10;
struct Edge{
	int u,v,w;
	bool operator<(const Edge&rhs)const{
		return w<rhs.w;
	}
};
int n,m,k,u,v,w,tot,i,j,fa[N],sz[N],son[N],f[N],bel[N],dep[N],val[N];
vector<Edge>edge;
vector<int>G[N];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
void dfs(int u){
	sz[u]=1,son[u]=-1;
	for (int i=0;i<(int)G[u].size();++i){
		int v=G[u][i];
		dep[v]=dep[u]+1,f[v]=u;
		dfs(v);
		sz[u]+=sz[v];
		if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int f){
	bel[u]=f;
	if (son[u]==-1) return;
	dfs2(son[u],f);
	for (int i=0;i<(int)G[u].size();++i){
		int v=G[u][i];
		if (v==son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int u,int v){
	for (;bel[u]!=bel[v];dep[bel[u]]>dep[bel[v]]?u=f[bel[u]]:v=f[bel[v]]);
	return dep[u]>dep[v]?v:u;
}
int main(){
	read(n),read(m),read(k);
	for (i=1;i<=n;++i) fa[i]=i;
	for (i=1;i<=m;++i){
		read(u),read(v),read(w);
		edge.PB((Edge){u,v,w});
	}
	sort(edge.begin(),edge.end());
	for (tot=n,i=0;i<(int)edge.size();++i){
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		int fu=Find(u),fv=Find(v);
		if (fu^fv){
			fa[fu]=fa[fv]=++tot;
			fa[tot]=tot;
			val[tot]=w;
			G[tot].PB(fu),G[tot].PB(fv);
		}
	}
	f[tot]=0,dfs(tot),dfs2(tot,tot);
	for (;k--;){
		read(u),read(v);
		printf("%d\n",val[lca(u,v)]);
	}
	return 0;
}