【UOJ274】【清华集训2016】温暖会指引我们前行
任务描述
虽然小R住的宿舍楼早已来了暖气，但是由于某些原因，宿舍楼中的某些窗户仍然开着（例如厕所的窗户），这就使得宿舍楼中有一些路上的温度还是很低。
小R的宿舍楼中有n个地点和一些路，一条路连接了两个地点，小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始，小R还不熟悉宿舍楼中的任何一条路，所以他会慢慢地发现这些路，他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。
小R需要在宿舍楼中活动，每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径，最温暖的路径的定义为，将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高，在满足该条件的情况下，温度第二低的路温度尽量高，以此类推。小R不会经过重复的路。由于每条路的温度互不相同，因此只存在一条最温暖的路径。
对于小R的每次活动，你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动，则输出 −1。
注意本题中的字典序与传统意义上的字典序定义有所不同，对于两个序列a,b(a≠b)，若a是b的前缀则a的字典序较大，同时可以推出空串的字典序最大。
输入格式
第一行两个正整数 n,m。表示小R的宿舍楼中有 n 个地点，共发生了 m 个事件。
接下来 m 行，每行描述一个事件，事件分为三类。
-
find id u v t l 表示小R发现了一条连接u和v之间的路，编号为id。相同id的边只会出现一次。
-
move u v 表示小R要从u到达v，你需要计算出最温暖的路径的长度 ，若不能从u到达v，则输出−1。
-
change id l 表示从u到v这条边的长度变为了l（保证在当前时间点这条边存在）。
输出格式
对于每个询问，输出一行整数，表示最温暖的路径长度。
题解：裸题，直接用LCT维护最大生成树即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
int n,m,tot;
struct LCT
{
int ch[2],fa,rev,v,vn,l,sl;
}s[maxn<<2];
int f[maxn],pa[maxn<<2],pb[maxn<<2];
char str[10];
inline bool isr(int x) {return (s[s[x].fa].ch[0]!=x)&&(s[s[x].fa].ch[1]!=x);}
inline void pushdown(int x)
{
if(s[x].rev)
{
swap(s[x].ch[0],s[x].ch[1]);
if(s[x].ch[0]) s[s[x].ch[0]].rev^=1;
if(s[x].ch[1]) s[s[x].ch[1]].rev^=1;
s[x].rev=0;
}
}
inline int MN(int a,int b) {return s[a].v<s[b].v?a:b;}
inline void pushup(int x)
{
s[x].vn=MN(MN(s[s[x].ch[0]].vn,s[s[x].ch[1]].vn),x);
s[x].sl=s[s[x].ch[0]].sl+s[s[x].ch[1]].sl+s[x].l;
}
inline void rotate(int x)
{
int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);
if(!isr(y)) s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
void updata(int x)
{
if(!isr(x)) updata(s[x].fa);
pushdown(x);
}
inline void splay(int x)
{
updata(x);
while(!isr(x))
{
int y=s[x].fa,z=s[y].fa;
if(!isr(y))
{
if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x)
{
for(int y=0;x;splay(x),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa);
}
inline void maker(int x)
{
access(x),splay(x),s[x].rev^=1;
}
inline void link(int x,int y)
{
maker(y),s[y].fa=x;
}
inline void cut(int x,int y)
{
maker(x),access(y),splay(y),s[y].ch[0]=s[x].fa=0,pushup(x),pushup(y);
}
int find(int x)
{
return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
//freopen("bz4736.in","r",stdin);
s[0].v=1<<30;
n=rd(),m=rd();
int i,a,b,c,e;
for(i=1;i<=n;i++) f[i]=i,s[i].v=1<<30,s[i].vn=i;
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='f')
{
e=n+rd()+1,a=pa[e]=rd()+1,b=pb[e]=rd()+1,s[e].v=rd(),s[e].vn=e,s[e].l=s[e].sl=rd();
if(find(a)==find(b))
{
maker(a),access(b),splay(b),c=s[s[b].ch[0]].vn;
if(s[c].v<s[e].v) cut(c,pa[c]),cut(c,pb[c]),link(a,e),link(b,e);
}
else f[f[a]]=f[b],link(a,e),link(b,e);
}
if(str[0]=='m')
{
a=rd()+1,b=rd()+1;
if(find(a)!=find(b)) puts("-1");
else maker(a),access(b),splay(b),printf("%d
",s[s[b].ch[0]].sl);
}
if(str[0]=='c') e=n+rd()+1,splay(e),s[e].l=rd(),pushup(e);
}
return 0;
}