记录编号	344951	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2016-11-10 17:32:43	内存使用	1.60 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20010,maxe=50010,maxq=30010;
struct edge{
	int from,to,w;
	bool operator<(const edge &e)const{return w>e.w;}
}e[maxe+maxn];
void Kruskal();
int findroot(int);
void mergeset(int,int);
void bfs();
int LCA(int,int);
int prt[maxn],size[maxn],depth[maxn],son[maxn],top[maxn];
int n,m,k,lc[maxn],rc[maxn],w[maxn],q[maxn],head,tail,x,y;
int main(){
#define MINE
#ifdef MINE
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
	for(int i=2;i<=n;i++){
		e[++m].from=1;
		e[m].to=i;
		e[m].w=-1;
	}
	Kruskal();
	bfs();
	scanf("%d",&k);
	while(k--){
		scanf("%d%d",&x,&y);
		printf("%d\n",w[LCA(x,y)]);
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void Kruskal(){
	for(int i=1;i<=n;i++)prt[i]=i;
	sort(e+1,e+m+1);
	for(int i=1;i<=m;i++)if(findroot(e[i].from)!=findroot(e[i].to)){
		n++;
		prt[n]=n;
		w[n]=e[i].w;
		lc[n]=findroot(e[i].from);
		rc[n]=findroot(e[i].to);
		mergeset(e[i].from,n);
		mergeset(e[i].to,n);
	}
}
int findroot(int x){return prt[x]==x?x:(prt[x]=findroot(prt[x]));}
void mergeset(int x,int y){prt[findroot(x)]=findroot(y);}
void bfs(){
	memset(prt,0,sizeof(prt));
	int x;
	head=tail=1;
	q[tail++]=n;
	while(head!=tail){
		x=q[head++];
		size[x]=1;
		if(lc[x]){
			prt[lc[x]]=x;
			depth[lc[x]]=depth[x]+1;
			q[tail++]=lc[x];
		}
		if(rc[x]){
			prt[rc[x]]=x;
			depth[rc[x]]=depth[x]+1;
			q[tail++]=rc[x];
		}
	}
	for(int i=n;i;i--){
		x=q[i];
		size[prt[x]]+=size[x];
		if(size[x]>size[son[prt[x]]])son[prt[x]]=x;
	}
	for(int i=1;i<=n;i++){
		x=q[i];
		if(x==son[prt[x]])top[x]=top[prt[x]];
		else top[x]=x;
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]])swap(x,y);
		x=prt[top[x]];
	}
	if(depth[x]>depth[y])swap(x,y);
	return x;
}
/*
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
Answer:
3
-1
3
*/