记录编号	252190	评测结果	AAAAAAAAAA
题目名称	图的询问	最终得分	100
用户昵称	bhiaibogf	是否通过	通过
代码语言	C++	运行时间	0.136 s
提交时间	2016-04-19 18:59:50	内存使用	2.89 MiB

#include <bits/stdc++.h>
using namespace std;

const int MAXN=15000+5,MAXM=30000+5,B=16,INF=0xc0c0c0c0;
int n,m,k;
int read(){
    int r=0;char c;bool sign=0;
    while(c=getchar(),c=='-'?sign=1:0,!isdigit(c));
    while(r=r*10+c-'0',isdigit(c=getchar()));
    return sign?-r:r;
}

vector<pair<int,int> > g[MAXN];
int f[MAXN][B+1],_max[MAXN][B+1],dep[MAXN];
void Add(int u,int v,int w){
    g[u].push_back(make_pair(w,v));
    g[v].push_back(make_pair(w,u));
}void DFS(int u,int p){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i].second,w=g[u][i].first;
        if(v==p) continue;
        f[v][0]=u;_max[v][0]=w;
        dep[v]=dep[u]+1;
        DFS(v,u);
    }
}int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int ans=INF;
    for(int i=B;~i;i--)
        if(dep[f[u][i]]>=dep[v]) ans=max(ans,_max[u][i]),u=f[u][i];
    if(u==v) return ans;
    for(int i=B;~i;i--)
        if(f[u][i]^f[v][i]) ans=max(ans,max(_max[u][i],_max[v][i])),u=f[u][i],v=f[v][i];
    ans=max(ans,max(_max[u][0],_max[v][0]));
    return ans;
}

struct Edge{
    int u,v,w;
    Edge() {}
    void Read() {u=read(),v=read(),w=read();}
    bool operator < (const Edge &b) const {return w<b.w;}
}e[MAXM];
int p[MAXN];
int P(int x) {return p[x]==x?x:p[x]=P(p[x]);}
void Union(int u,int v){
    int pu=P(u),pv=P(v);
    p[pu]=pv;
}void Kruskal(){
    sort(e,e+m);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(P(u)==P(v)) continue;
        Add(u,v,w);
        Union(u,v);
    }
}void Init(){
    n=read();m=read();k=read();
    for(int i=0;i<m;i++) e[i].Read();
    Kruskal();
    memset(_max,0xc0,sizeof _max);
    dep[1]=1; DFS(1,-1);
    for(int j=1;j<=B;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1],_max[i][j]=max(_max[i][j-1],_max[f[i][j-1]][j-1]);
}

int main(){
#ifdef bhiaibogf
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#else
    freopen("heatwave.in","r",stdin);
    freopen("heatwave.out","w",stdout);
#endif
    Init();
    //for(int i=1;i<=n;i++){
        //cout<<i<<endl;
        //for(int j=0;j<=B;j++)
            //cout<<f[i][j]<<' '<<_max[i][j]<<endl;
    //}
    while(k--){
        int u=read(),v=read();
        //cout<<u<<' '<<v<<endl;
        printf("%d\n",LCA(u,v));
    }
    return 0;
}