记录编号	252137	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2016-04-19 16:16:39	内存使用	1.93 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int SIZEN=15010,SIZEM=30010,INF=0x7fffffff/2;
vector<int> s[SIZEN];
int N,M,K;
class miku
{
public:
	int fr,to,w;
}E[SIZEM],D[SIZEN];
void read()
{
	scanf("%d%d%d",&N,&M,&K);
	for(int i=1;i<=M;i++) scanf("%d%d%d",&E[i].fr,&E[i].to,&E[i].w);
}
int org[SIZEN],rank[SIZEN];
int tot=0;
int find(int x)
{
	if(x==org[x]) return x;
	return org[x]=find(org[x]);
}
void add(int fr,int to,int w)
{
	s[fr].push_back(tot);D[tot++]=(miku){fr,to,w};
	s[to].push_back(tot);D[tot++]=(miku){to,fr,w};
}
void link(int a,int b,int w)
{
	//cout<<a<<" "<<b<<" "<<w<<endl;
	int x=find(a),y=find(b);
	if(org[x]==org[y]) return;
	add(a,b,w);
	if(rank[x]>rank[y]) org[y]=x;
	else org[x]=y;
	if(rank[x]==rank[y]) rank[x]++;
}
bool cmp(miku a,miku b)
{
	return a.w<b.w;
}
int fa[SIZEN]={0},top[SIZEN],dep[SIZEN]={0};
int pos[SIZEN],siz[SIZEN],son[SIZEN]={0};
void dfs(int x)
{
	dep[x]=dep[fa[x]]+1;
	siz[x]=1;
	for(int i=0;i<s[x].size();i++)
	{
		int v=D[s[x][i]].to;
		if(v==fa[x]) continue;
		fa[v]=x;
		dfs(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]]) son[x]=v;
	}
}
int totw=0;
void maketree(int x,int tp)
{
	//cout<<x<<" "<<tp<<endl;
	top[x]=tp;pos[x]=++totw;
	if(son[x]) maketree(son[x],tp);
	for(int i=0;i<s[x].size();i++)
	{
		int v=D[s[x][i]].to;
		if(v==fa[x]||v==son[x]) continue;
		maketree(v,v);
	}
}
class poi
{
public:
	int l,r;
	int mi;
}tr[SIZEN*4];
void built(int rt,int l,int r)
{
	tr[rt].l=l;tr[rt].r=r;
	tr[rt].mi=-INF;
	if(l<r)
	{
		int mid=(l+r)/2;
		built(rt<<1,l,mid);
		built(rt<<1|1,mid+1,r);
	}
}
void seg_built(int rt,int k,int w)
{
	if(tr[rt].l==tr[rt].r) 
	{
		tr[rt].mi=w;
		return;
	}
	int mid=(tr[rt].l+tr[rt].r)/2;
	if(k<=mid) seg_built(rt<<1,k,w);
	else seg_built(rt<<1|1,k,w);
	tr[rt].mi=max(tr[rt<<1].mi,tr[rt<<1|1].mi);
}
void prepare()
{
	dfs(1);
	//for(int i=1;i<=N;i++) cout<<son[i]<<" "<<siz[i]<<" "<<pos[i]<<endl;
	maketree(1,1);
	built(1,1,N);
	for(int i=0;i<tot;i+=2) 
	{
		int fr=D[i].fr,to=D[i].to;
		if(dep[fr]>dep[to]) swap(fr,to);
		seg_built(1,pos[to],D[i].w);
	}
}
int query(int rt,int l,int r)
{
	int re;
	if(l>tr[rt].r||r<tr[rt].l) return -INF;
	if(l<=tr[rt].l&&tr[rt].r<=r) return tr[rt].mi;
	re=max(query(rt<<1,l,r),query(rt<<1|1,l,r));
	return re;
}
int get(int A,int B)
{
	int x=top[A],y=top[B];
	int ans=-INF;
	while(x!=y)
	{
		if(dep[x]<dep[y]) swap(x,y),swap(A,B);
		ans=max(ans,query(1,pos[x],pos[A]));
		A=fa[x];x=top[A];
	}
	if(A!=B) 
	{
		if(dep[A]<dep[B]) swap(A,B);
		ans=max(ans,query(1,pos[son[B]],pos[A]));
	}
	return ans;
}
void work()
{
	sort(E+1,E+1+M,cmp);
	for(int i=1;i<=N;i++) org[i]=i;
	for(int i=1;i<=M;i++) link(E[i].fr,E[i].to,E[i].w);
	prepare();
	for(int i=1;i<=K;i++)
	{
		int A,B;
		scanf("%d%d",&A,&B);
		int ans=get(A,B);
		printf("%d\n",ans);
	}
}
int main()
{
	freopen("heatwave.in","r",stdin);
	freopen("heatwave.out","w",stdout);
	read();
	work();
	return 0;
}