学步园

例：bzoj 3732 network

发现自己以前YY的倍增写错了，导致速度慢了近10倍，现已改

//#define _TEST _TEST  
#include <cstdio>  
#include <cstring>  
#include <cstdlib>  
#include <iostream>  
#include <cmath>  
#include <algorithm>  
using namespace std;  
/////////////////////////////////////////////////  
#define rep(i,l,r) for(int i=l;i<=r;i++)  
#define per(i,r,l) for(int i=r;i>=l;i--)  
#define MS(arr,x) memset(arr,x,sizeof(arr))  
#define LL long long  
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)  
/////////////////////////////////////////////////  
//O(mlogm+nlogn+qlogn)   
const int inf=0x3f3f3f3f;  
const int maxn=15010;  
const int maxm=30010;  
int n,m,q;  
  
namespace Tree//Tree声明   
{         //////////////////////////////////  
struct edge{int v,w,next;}e[maxm];  
int head[maxn],k;  
inline void adde(int u,int v,int w){e[k].v=v;e[k].w=w;e[k].next=head[u];head[u]=k++;}  
bool vis[maxn];  
  
int dis[maxn][16];  
int fa[maxn][16];  
int dep[maxn];  
}         //////////////////////////////////  
namespace MST//MST声明   
{         //////////////////////////////////  
struct edge{int u,v,w;}e[maxm*2];  
int k=0;  
inline void adde(int u,int v,int w){e[k].u=u;e[k].v=v;e[k].w=w;k++;}  
inline bool cmp(edge a,edge b){return a.w<b.w;}  
int cnt;//联通块   
int fa[maxn];  
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}  
inline bool unio(int u,int v)  
{  
     int fu=find(u),fv=find(v);  
     if(fv==fu)return 0;  
     fa[fu]=fv;  
     return 1;  
}  
}         //////////////////////////////////  
namespace MST//MST定义   
{         //////////////////////////////////  
void cal()  
{  
     sort(&e[0],&e[k],cmp);  
     rep(i,1,n) fa[i]=i;  
     cnt=n;  
     rep(i,0,m-1)  
     {  
         if(unio(e[i].u,e[i].v)) cnt--,Tree::adde(e[i].u,e[i].v,e[i].w),Tree::adde(e[i].v,e[i].u,e[i].w);  
         if(cnt<=1) break;  
     }  
}  
}         //////////////////////////////////  
namespace Tree//Tree定义   
{         //////////////////////////////////  
void dfs(int u,int depth)  
{  
     dep[u]=depth;  
     INE(i,u,e)  
     {  
         int v=e[i].v;  
         if(dep[v]) continue;  
         dis[v][0]=e[i].w;  
         fa[v][0]=u;  
         rep(i,1,15) dis[v][i]=max(dis[v][i-1],dis[fa[v][i-1]][i-1]),
                     fa[v][i]=fa[fa[v][i-1]][i-1];
         dfs(v,depth+1);  
     }  
}  
void init()  
{
     rep(i,1,n) if(!dep[i]) dfs(i,0);
}  
int query(int u,int v)  
{  
    if(MST::find(u)!=MST::find(v)) return -1;  
    int ans=0;  
    if(dep[u]<dep[v]) swap(u,v);
    int d=dep[u]-dep[v];
    rep(i,0,15) if((1<<i)&d)
    {
        ans=max(ans,dis[u][i]);
        u=fa[u][i];
    }
    if(u==v) return ans;
    per(i,15,0)
    {
        if(fa[u][i]!=fa[v][i])
        {
            ans=max(ans,max(dis[u][i],dis[v][i]));
            u=fa[u][i],v=fa[v][i];
        }
    }
    ans=max(ans,max(dis[u][0],dis[v][0]));
    return ans;
}  
}         //////////////////////////////////  
/////////////////////////////////////////////////  
  
/////////////////////////////////////////////////  
void input()  
{  
     MS(Tree::head,-1);  
     MS(Tree::fa,-1);  
       
     using namespace MST;  
     scanf("%d%d%d",&n,&m,&q);  
     int u,v,w;  
     rep(i,1,m)  
     {  
         scanf("%d%d%d",&u,&v,&w);  
         adde(u,v,w);  
     }  
}  
void solve()  
{  
     ///////////////////init///////////////////  
     int u,v;  
     ////////////////calculate////////////////  
     MST::cal();
     Tree::init();
     while(q--)  
     {  
         scanf("%d%d",&u,&v);  
         printf("%d\n",Tree::query(u,v));  
     }  
     /////////////////output/////////////////  
       
}  
/////////////////////////////////////////////////  
int main()  
{  
     #ifndef _TEST  
     freopen("3732.in","r",stdin); freopen("3732.out","w",stdout);  
     #endif  
     input();  
     solve();  
     #ifdef _TEST  
     for(;;);  
     #endif  
     return 0;  
}