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

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define M 30010
#define N 16600
using namespace std;
ifstream in("heatwave.in");
ofstream out("heatwave.out");
int n,m,q;
int fa[N]={0},size[N]={0},top[N]={0};
int deep[N]={0},hash[N]={0},son[N]={0};
int val[N]={0};
bool vis[N]={0};
vector<int> G[N];
vector<int> C[N];
int INF=(1<<29);
class rangetree
{
public:
	int mi[4*N],ma[4*N];
	void clear()
	{
		memset(mi,0,sizeof(mi));
		memset(ma,0,sizeof(ma));
	}
	void pushup(int o)
    {
		mi[o]=min(mi[o<<1],mi[o<<1|1]);
		ma[o]=max(ma[o<<1],ma[o<<1|1]);
	}
	void modify(int o,int l,int r,int x,int val)
	{
		if(l==r)
		{
			mi[o]=val;
			ma[o]=val;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid)modify(o<<1,l,mid,x,val);
		else modify(o<<1|1,mid+1,r,x,val);
		pushup(o);
	}
	int minquery(int o,int l,int r,int ql,int qr)
	{
		if(ql<=l&&r<=qr)return mi[o];
		int ans=INF;
		int mid=(l+r)>>1;
		if(ql<=mid)ans=min(ans,minquery(o<<1,l,mid,ql,qr));
		if(mid<qr)ans=min(ans,minquery(o<<1|1,mid+1,r,ql,qr));
		return ans;
	}
	int maxquery(int o,int l,int r,int ql,int qr)
	{
		if(ql<=l&&r<=qr)return ma[o];
		int ans=-INF;
		int mid=(l+r)>>1;
		if(ql<=mid)ans=max(ans,maxquery(o<<1,l,mid,ql,qr));
		if(mid<qr)ans=max(ans,maxquery(o<<1|1,mid+1,r,ql,qr));
		return ans;
	}
}A;
class edge
{
public:
	int u,v,w;
	void make(int a,int b,int c){u=a;v=b;w=c;}
	void print()
	{
		out<<u<<' '<<v<<' '<<w<<endl;
	}
}E[M];
bool operator <(edge a,edge b)
{
	return a.w<b.w;
}
int ufs(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=ufs(fa[x]);
}
void clear(){for(int i=1;i<=n;i++)fa[i]=i;}
void read()
{
	int i,u,v,w;
	in>>n>>m>>q;
	for(i=1;i<=m;i++)
	{
		in>>u>>v>>w;
		E[i].make(u,v,w);
	}
}
void Kruskal()
{
	int i,u,v,w,a,b;
	sort(E+1,E+m+1);
	clear();
	for(i=1;i<=m;i++)
	{
		u=E[i].u;v=E[i].v;w=E[i].w;
		a=ufs(u);b=ufs(v);
		if(a!=b)
		{
			fa[a]=b;
			//out<<u<<' '<<v<<' '<<w<<endl;
			G[u].push_back(v);
			G[v].push_back(u);
			C[u].push_back(w);
			C[v].push_back(w);
			//out<<u<<' '<<v<<endl;
		}
	}
	//for(i=1;i<=m;i++)E[i].print();
}
void DFS1(int u)
{
    int i,v,w;
	vis[u]=1;
	size[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		w=C[u][i];
		if(!vis[v])
		{
			deep[v]=deep[u]+1;
			fa[v]=u;
			val[v]=w;
			DFS1(v);
			size[u]+=size[v];
			if(size[v]>size[son[u]])son[u]=v;
		}
	}
}
int tot=0;
void DFS2(int u,int tp)
{
	hash[u]=++tot;
	top[u]=tp;
	vis[u]=1;
	if(son[u])DFS2(son[u],tp);
    for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!vis[v])DFS2(v,v);
	}
}
void init()
{
	memset(fa,0,sizeof(fa));
	DFS1(1);
	memset(vis,0,sizeof(vis));
	DFS2(1,1);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)A.modify(1,1,n,hash[i],val[i]);
}
int maxquery(int u,int v)
{
	int f1,f2;
	int ans=-INF;
	f1=top[u];f2=top[v];
	while(f1!=f2)
	{
		if(deep[f1]<deep[f2])
		{
			swap(f1,f2);
			swap(u,v);
		}
		
		ans=max(ans,A.maxquery(1,1,n,hash[f1],hash[u]));
		u=fa[f1];f1=top[u];
	}
	if(u!=v)
	{
		if(deep[u]>deep[v])swap(u,v);
		ans=max(ans,A.maxquery(1,1,n,hash[son[u]],hash[v]));
	}
	return ans;
}
int minquery(int u,int v)
{
	int f1,f2;
	int ans=INF;
	f1=top[u];f2=top[v];
	while(f1!=f2)
	{
		if(deep[f1]<deep[f2])
		{
			swap(f1,f2);
			swap(u,v);
		}
		
		ans=min(ans,A.minquery(1,1,n,hash[f1],hash[u]));
		u=fa[f1];f1=top[u];
	}
	if(u!=v)
	{
		if(deep[u]>deep[v])swap(u,v);
		ans=min(ans,A.minquery(1,1,n,hash[son[u]],hash[v]));
	}
	return ans;
}
void work()
{
	int i,u,v;
	for(i=1;i<=q;i++)
	{
		in>>u>>v;
		out<<maxquery(u,v)<<endl;
	}
}
int main()
{
	read();
	Kruskal();
	init();
	work();
	return 0;
}