记录编号	336641	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.310 s
提交时间	2016-11-03 15:45:03	内存使用	4.27 MiB

#include<cstdio>
#include<iostream>
#include<cstring> 
#include<vector>
#include<algorithm>	
using namespace std;
const int maxn=45050;
int n,m,k; 
struct edge
{
	int x,y,z;
};
edge t[maxn];
vector<int> f[maxn],g[maxn];
int T_max[maxn*4]; 
int fa[maxn],x,y,z,dfs_clock;
int fath[maxn],deep[maxn],dist[maxn],son[maxn],id[maxn],dfn[maxn],top[maxn],to[maxn],sz[maxn];
int find(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
bool cmp(const edge &a,const edge &b)
{
	return a.z<b.z;	
} 
void Kruskal()
{
	int cnt=n;
	sort(t+1,t+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(cnt==1) return;
		int fx=find(t[i].x);
		int fy=find(t[i].y);
		if(fx!=fy)
		{
			fa[fx]=fy;
			f[t[i].x].push_back(t[i].y);
			f[t[i].y].push_back(t[i].x);
			g[t[i].x].push_back(t[i].z);
			g[t[i].y].push_back(t[i].z);
			cnt--;
		}
	}
}
void dfs1(int u,int fat,int dep,int dis)
{
	fath[u]=fat;dist[u]=dis;
	deep[u]=dep;sz[u]=1;
	for(int i=0;i<f[u].size();i++)
	{
		int v=f[u][i];
		if(v==fat) continue;
		to[v]=g[u][i];
		dfs1(v,u,dep+1,dis+g[u][i]);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])
			son[u]=v;
	}
} 
void dfs2(int u,int tp)
{
	top[u]=tp;
	id[u]=++dfs_clock;
	dfn[dfs_clock]=u; 
	if(son[u]) dfs2(son[u],tp); 
	for(int i=0;i<f[u].size();i++)
	{
		int v=f[u][i];
		if(v==fath[u]||v==son[u]) continue;
		dfs2(v,v); 
	} 
}
int query_max(int rt,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)
    {
        return T_max[rt];
    }
    int mid=(l+r)>>1,ans=0;
    if(x<=mid) ans=max(ans,query_max(rt<<1,l,mid,x,y));
    if(y>mid) ans=max(ans,query_max(rt<<1|1,mid+1,r,x,y));
    return ans;
}
int get_max(int u,int v)
{
    int ans=0;
    int x=top[u],y=top[v];
    while(x!=y)
    {
        if(deep[x]<deep[y])
        {
            swap(u,v);swap(x,y);
        }
        ans=max(ans,query_max(1,1,n,id[x],id[u]));
        u=fath[x];x=top[u];
    }
    if(deep[u]>deep[v]) swap(u,v);
    return max(ans,query_max(1,1,n,id[son[u]],id[v]));
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        T_max[rt]=to[dfn[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    T_max[rt]=max(T_max[rt<<1],T_max[rt<<1|1]);
}
int main()
{
	freopen("heatwave.in","r",stdin);
	freopen("heatwave.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].z);
	}
	Kruskal();
	dfs1(1,0,0,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",get_max(x,y)); 
	}
	return 0; 
}