记录编号	336252	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2016-11-03 06:31:18	内存使用	4.92 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 45000 + 10;
int n,m,k,tot,head[maxn],x,y,z,cnt,L,R,top[maxn],id[maxn],maxnum[maxn<<2];
int size[maxn],fa[maxn],dis[maxn],deep[maxn],son[maxn],dfn[maxn],f[maxn];
int read(){
	int 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 Edge{
	int to,next,dis,from;
}edge[maxn<<1],e[maxn<<1];
void Addedge(int x,int y,int z)
{
	edge[++tot].to=y;
	edge[tot].dis=z;
	edge[tot].next=head[x];
	head[x]=tot;
}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool cmp(const Edge & x , const Edge & y ){
	return x.dis < y.dis;
}
void Krusal(){
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++){
		int f1=find(e[i].from),f2=find(e[i].to);
		if(f1!=f2){
			f[f2]=f1;
			Addedge(e[i].from,e[i].to,e[i].dis);
			Addedge(e[i].to,e[i].from,e[i].dis);
		}
	}
}
void dfs(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(size[p])continue;
		fa[p]=x;
		dis[p]=edge[i].dis;
		deep[p]=deep[x]+1;
		dfs(p);
		size[x]+=size[p];
		if(size[p]>size[son[x]])son[x]=p;
	}
}
void dfs2(int x,int tp){
	dfn[x]=++cnt;top[x]=tp;id[cnt]=x;
	if(son[x])dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!dfn[p])dfs2(p,p);
	}
}
void build(int rt,int l,int r){
	if(l==r){maxnum[rt]=dis[id[l]] ;return;}
	int mid = (l+r)>>1;
	build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
	maxnum[rt]=max(maxnum[rt<<1],maxnum[rt<<1|1]);
}
int query_max(int rt,int l,int r){
	if( L <= l && R >= r)return maxnum[rt];
	int mid=(l+r)>>1,ans=-0x7f7f7f7f;
	if(L<=mid)ans=max(ans,query_max(rt<<1,l,mid));
	if(R>mid)ans=max(ans,query_max(rt<<1|1,mid+1,r));
	return ans;
}
int Query_max(int x,int y){
	int ans=-0x7f7f7f7f ;
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])std::swap(x,y);
		L=dfn[top[x]],R=dfn[x] ;
		ans=max(ans,query_max(1,1,n));
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	L=dfn[son[x]],R=dfn[y];
	ans=max(ans,query_max(1,1,n));
	return ans;
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(deep[x]<deep[y])return x;
	else return y;
}
int main(){
	freopen("heatwave.in","r",stdin);
	freopen("heatwave.out","w",stdout);
	n=read();m=read();k=read();
	for(int i=1;i<=m;i++){
		x=read();y=read();z=read();
		e[i].from=x; e[i].to=y; e[i].dis=z;
	}
	sort(e+1,e+1+m,cmp); Krusal();
	deep[1]=1;dfs(1);dfs2(1,1);	 build(1,1,n);
	while(k--){
		x=read();y=read();
		printf("%d\n",Query_max(x,y));
	//	printf("%d\n",dis[x]+dis[y]-2*dis[lca(x,y)]);
	}
//	system("pause");
}