[STEP5] 0149 : 轎夫

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define N 200005
struct P{
    int x,y,c;
}s[N];
int p[N],n,ans[N],vi[N]={0},cnt[N],dfs_cnt;
int f(int k){
    if(p[k]==k) return k;
    return p[k]=f(p[k]);
}
int cmp(P a,P b){
    return  a.c<b.c;
}
struct T{
    int v,c;
}dp[N][20];
vector<T> vec[N];
void dfs(int u,int fa,int tmp,int add){
    int i;
    cnt[u]=add;
    dp[u][0].v=fa;
    dp[u][0].c=tmp;
    for(i=0;i<vec[u].size();i++){
        T v=vec[u][i];
        if(vi[v.v]==0){
            vi[v.v]=1;
            dfs(v.v,u,v.c,add+1);
        }
    }
}
int main(){
    int i,j,m,k,x,y,ans,d;
    scanf("%d%d%d",&n,&m,&k);
    memset(dp,-1,sizeof(dp));
    for(i=1;i<=n;i++)
        p[i]=i;
    for(i=0;i<m;i++){
        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].c);
    }
    sort(s,s+m,cmp);
    for(i=0;i<m;i++){
        x=f(s[i].x);
        y=f(s[i].y);
        if(x!=y){
            vec[x].push_back((T){y,s[i].c});
            vec[y].push_back((T){x,s[i].c});
            p[x]=y;
        }
    }
    for(i=1;i<=1;i++){
        if(vi[i]==0){
            vi[i]=1;
            dfs_cnt=0;
            dfs(i,-1,-1,0);
        }
    }

    for(i=1;i<=19;i++)
    for(j=1;j<=n;j++){
        int v=dp[j][i-1].v;
        if(v!=-1){
            dp[j][i].v=dp[v][i-1].v;
            dp[j][i].c=max(dp[j][i-1].c,dp[v][i-1].c);
        }
    }
    for(i=0;i<k;i++){
        scanf("%d%d",&x,&y);
        ans=0;
        if(cnt[x]>cnt[y]) swap(x,y);
        d=cnt[y]-cnt[x];
        for(j=19;j>=0;j--){
            if(d&(1<<j)){
                ans=max(ans,dp[y][j].c);
                y=dp[y][j].v;
            }
        }
        for(j=19;j>=0;j--){
            if(dp[x][j].v!=dp[y][j].v){
                ans=max(ans,dp[x][j].c);
                x=dp[x][j].v;
                ans=max(ans,dp[y][j].c);
                y=dp[y][j].v;
            }
        }
        if(x!=y){
            ans=max(ans,dp[x][0].c);
            ans=max(ans,dp[y][0].c);
        }
        printf("%d\n",ans);
    }
}