题目大意：给定一个n个点m条边的无向连通图。k次询问两点之间全部路径中最长边的最小值
LCT的裸题！
首先维护一个动态的最小生成树，然后每次增加边时删除两点间路径上权值最大的边。最后询问时直接求x到y链上的最大权值就可以。水爆了！
！
。
。。
好吧开玩笑的 真正的题解见http://blog.****.net/popoqqq/article/details/39755703
我仅仅是闲得无聊水一发LCT罢了0.0
TLE了好久。。。
由于有边权为0的边我没更新。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 15010
#define INF 2147483647
using namespace std;
struct edge{
int x,y,z;
}e[M<<1];
struct abcd{
abcd *fa,*ls,*rs;
int num,maxedge;
bool rev_mark;
abcd(int x);
void Reverse();
void Push_Up();
void Push_Down();
}*null=new abcd(0),*tree[M],*edges[M<<1];
abcd :: abcd(int x)
{
fa=ls=rs=null;
num=maxedge=x;
rev_mark=0;
}
void abcd :: Reverse()
{
rev_mark^=1;
swap(ls,rs);
}
void abcd :: Push_Up()
{
int maxnum=-1;
if(e[ls->maxedge].z>maxnum)
maxnum=e[ls->maxedge].z,maxedge=ls->maxedge;
if(e[rs->maxedge].z>maxnum)
maxnum=e[rs->maxedge].z,maxedge=rs->maxedge;
if(e[num].z>maxnum)
maxedge=num; }
void abcd :: Push_Down()
{
if(fa->ls==this||fa->rs==this)
fa->Push_Down();
if(rev_mark)
{
ls->Reverse();
rs->Reverse();
rev_mark=0;
}
}
void Zig(abcd *x)
{
abcd *y=x->fa;
y->ls=x->rs;
x->rs->fa=y;
x->rs=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
}
void Zag(abcd *x)
{
abcd *y=x->fa;
y->rs=x->ls;
x->ls->fa=y;
x->ls=y;
x->fa=y->fa;
if(y==y->fa->ls)
y->fa->ls=x;
else if(y==y->fa->rs)
y->fa->rs=x;
y->fa=x;
y->Push_Up();
}
void Splay(abcd *x)
{
x->Push_Down();
while(x->fa->ls==x||x->fa->rs==x)
{
abcd *y=x->fa,*z=y->fa;
if(x==y->ls)
{
if(y==z->ls)
Zig(y);
Zig(x);
}
else
{
if(y==z->rs)
Zag(y);
Zag(x);
}
}
x->Push_Up();
}
void Access(abcd *x)
{
abcd *y=null;
while(x!=null)
{
Splay(x);
x->rs=y;
x->Push_Up();
y=x;
x=x->fa;
}
}
abcd* Find_Root(abcd *x)
{
while(x->fa!=null)
x=x->fa;
return x;
}
void Move_To_Root(abcd *x)
{
Access(x);
Splay(x);
x->Reverse();
}
void Link(abcd *x,abcd *y)
{
Move_To_Root(x);
x->fa=y;
}
void Cut(abcd *x,abcd *y)
{
Move_To_Root(x);
Access(y);
Splay(y);
x->fa=null;
y->ls=null;
y->Push_Up();
}
int Query(abcd *x,abcd *y)
{
Move_To_Root(x);
Access(y);
Splay(y);
return y->maxedge;
}
int n,m,k;
void Insert(abcd *x,abcd *y,int pos)
{
if(e[pos].x==e[pos].y)
return ;
if( Find_Root(x)==Find_Root(y) )
{
int temp=Query(x,y);
if(e[temp].z<=e[pos].z)
return;
Cut(edges[temp],tree[e[temp].x]);
Cut(edges[temp],tree[e[temp].y]);
}
//if( Find_Root(x)==Find_Root(y) )
// printf("%d\n",1/0);
Link(x,edges[pos]);
Link(y,edges[pos]);
}
int main()
{
int i,x,y;
cin>>n>>m>>k;
for(i=1;i<=n;i++)
tree[i]=new abcd(0);
for(i=1;i<=m;i++)
edges[i]=new abcd(i);
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
Insert(tree[e[i].x],tree[e[i].y],i);
}
for(i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n", e[Query(tree[x],tree[y])].z );
}
}