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

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

const int MAXN=15000+5,MAXM=30000+5,BIT=14;
int read(){
    int r=0;char c;
    while(!isdigit(c=getchar()));
    while(r=r*10+c-'0',isdigit(c=getchar()));
    return r;
}int n,m,k;
int dep[MAXN],f[MAXN][BIT+1],_max[MAXN][BIT+1];
vector<int> g[MAXN];
struct Edge{
    int u,v,w;
    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]||p[x]==x)?x:p[x]=P(p[x]);}
void DFS(int u){
    for(int i=0;i<g[u].size();i++){
        Edge &ee=e[g[u][i]];
        int v=ee.u==u?ee.v:ee.u,w=ee.w;
        if(v==f[u][0]) continue;
        dep[v]=dep[u]+1;
        f[v][0]=u; _max[v][0]=w;
        DFS(v);
    }
}void Kruscal(){
    sort(e,e+m);
    for(int i=0;i<m;i++){
        int u=e[i].u,v=e[i].v;
        int fu=P(u),fv=P(v);
        if(fu!=fv) g[u].push_back(i),g[v].push_back(i);
        p[fu]=fv;
    }
}void Init(){
    n=read();m=read();k=read();
    for(int i=0;i<m;i++) e[i].Read();
    Kruscal();
    dep[1]=1;
    DFS(1);
    for(int j=1;j<=BIT;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 LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int ans=0;
    for(int i=BIT;~i;i--)
        dep[f[u][i]]>=dep[v]?(ans=max(ans,_max[u][i]),u=f[u][i]):0;//别忘=...
    if(u==v) return ans;
    for(int i=BIT;~i;i--)
        f[u][i]^f[v][i]?(ans=max(ans,max(_max[u][i],_max[v][i])),u=f[u][i],v=f[v][i]):0;
    ans=max(ans,max(_max[u][0],_max[v][0]));
    return ans;
}

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<<":\n";
        //for(int j=0;j<=BIT;j++)
            //cout<<_max[i][j]<<' ';
        //puts("");
    //}
    while(k--){
        int u=read(),v=read();
        printf("%d\n",LCA(u,v));
    }
    return 0;
}