记录编号	158398	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2015-04-14 19:02:46	内存使用	23.56 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
const int maxn=200010;
char ch[10000000],*ptr=ch;
struct edge{
	int x,y,v;
}e[maxn];
int n,m,k,q[maxn],f[maxn],val[maxn];
int M,tot,head[maxn],to[maxn],next[maxn],len[maxn];
int w[maxn],tr[maxn],fa[maxn],dep[maxn],siz[maxn],top[maxn],son[maxn],ans[maxn];
void swap(int &x,int &y){
	x^=y,y^=x,x^=y;
}
inline void ins(const int &u,const int &v,const int &w){
	to[++tot]=v,next[tot]=head[u],len[tot]=w,head[u]=tot;
}
inline bool cmp(const edge &a,const edge &b){
	return a.v>b.v;
}
inline int max(const int &x,const int &y){
	if(x<y) return x;
	return y;
}
inline int _find(const int &x){
	if(f[x]!=x) return f[x]=_find(f[x]);
	return x;
}
inline int read(){
	static int x;x=0;
	while(*ptr<48)ptr++;while(*ptr>47)x=x*10+*ptr++-48;
	return x;
}
inline int ask(int s,int t){
	static int res;res=1e8;
	for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) res=max(res,tr[s^1]);
		if( t&1) res=max(res,tr[t^1]);
	}
	return res;
}
inline int query(int u,int v){
	static int res;res=1e8;
	for(int fu=top[u],fv=top[v];fu!=fv;u=fa[fu],fu=top[u]){
		if(dep[fu]<dep[fv]) swap(fu,fv),swap(u,v);
		res=max(res,ans[u]);
	}
	if(u==v) return res;
	if(dep[u]>dep[v]) swap(u,v);return max(res,ask(w[u]+1,w[v]));
}
int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	fread(ch,1,10000000,stdin);
	n=read(),m=read();
	for(int i=1;i<=n;i++) f[i]=i;
	for(int u,v,ww,i=0;i<m;i++) u=read(),v=read(),ww=read(),e[i]=(edge){u,v,ww};
	std::sort(e,e+m,cmp);for(M=1;M<n+2;M<<=1);
	for(int u,v,i=0,j=1;i<m&&j<n;i++){
		u=_find(e[i].x),v=_find(e[i].y);
		if(u!=v) j++,f[v]=u,ins(e[i].x,e[i].y,e[i].v),ins(e[i].y,e[i].x,e[i].v);
	}
	int l=1,r=0,u;
	for(int j=1;j<=n;j++)
		if(_find(j)==j){
			q[++r]=j;
			while(l<=r){
				u=q[l++],siz[u]=1;
				for(int i=head[u];i;i=next[i])
					if(to[i]!=fa[u])
						dep[to[i]]=dep[u]+1,fa[to[i]]=u,q[++r]=to[i],val[to[i]]=len[i];
			}		
		}
	for(int i=n;i;i--){
		u=q[i];
		for(int j=head[u];j;j=next[j])
			if(to[j]!=fa[u]){
				siz[u]+=siz[to[j]];
				if(siz[to[j]]>siz[son[u]]) son[u]=to[j];
			}
	}
	for(int cnt=0,i=1;i<=n;i++){
		u=q[i];
		if(son[fa[u]]!=u){
			top[u]=u,ans[u]=val[u],w[u]=++cnt,tr[M+cnt]=val[u],u=son[u];
			while(u) ans[u]=max(ans[fa[u]],val[u]),w[u]=++cnt,tr[M+cnt]=val[u],u=son[u];
		}
		else top[u]=top[fa[u]];
	}
	for(int i=M-1;i;i--) tr[i]=max(tr[i<<1],tr[i<<1|1]);
	k=read();while(k--){
		l=read(),r=read();
		if(f[l]!=f[r]) puts("-1");
		else printf("%d\n",query(l,r));
	}
}