http://uoj.ac/problem/274
https://www.luogu.com.cn/problem/P6664
根据题目的条件（温度各不相同）和要求（温度排序后字典序最小），容易推出，实际上每次询问就是要求两个端点之间最低温度最高的，同时不存在环（就是在最低温最高基础上最短）的一条路径
其实和 水管局长 那题比较像，有连边操作，想到用 lct 维护，对于每个新加入的边：
- 如果它两端点还没有联通，直接连边即可。
- 如果两端点已经联通了，求出两端点之间路径中最低温度，如果新边的温度低于此值，不用管（因为不存在删边，所以不可能走到这条新边）。否则，就把原路径中最低温的边断开，并连接新边。
这样做的正确性也就比较显然，其实就是维护一个最大生成树
还需要一个技巧来维护边的信息，就是为每一个边新建一个虚拟节点，权值（在这里是长度）为边权。
然后连边时就用这个虚拟节点和它两个端点相连，端点（实际节点）的点权为 (0)，就能正常维护信息了。
这样修改操作就把那条边的虚拟节点伸展到 lct 的根，然后更新。
查询先看是否联通，如果联通就把那条路径 split 出来，查询长度和。
为了方便找路径中最低温的边是哪个，节点结构体中的 min 其实是最低温边的标号。
代码，洛谷UOJ都能过，而且似乎并不像网上博客说的一样需要刻意卡常
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 100005
#define M 300005
int n,m;
int tem[M];
struct tr{
tr *son[2],*fa;
int tag;
int sumlen,len,min,thismin;
}*null,*pos[N+M],dizhi[N+M];
int U[M],V[M];
#define ident(tree,fa) (fa->son[1]==tree)
#define notroot(tree) (tree->fa->son[0]==tree||tree->fa->son[1]==tree)
#define min(x,y) (tem[x]<tem[y]?x:y)
inline void connect(tr *tree,tr *fa,int k){fa->son[k]=tree;tree->fa=fa;}
inline void pushdown(tr *tree){
if(!tree->tag) return;
tree->son[0]->tag^=1;tree->son[1]->tag^=1;
std::swap(tree->son[0],tree->son[1]);
tree->tag=0;
}
inline void pushup(tr *tree){
tree->sumlen=tree->len+tree->son[0]->sumlen+tree->son[1]->sumlen;
tree->min=min(tree->thismin,min(tree->son[0]->min,tree->son[1]->min));
}
inline void rotate(tr *tree){
tr *fa=tree->fa,*faa=fa->fa;
pushdown(fa);pushdown(tree);
int k=ident(tree,fa);
connect(tree->son[k^1],fa,k);
tree->fa=faa;
if(notroot(fa)) faa->son[ident(fa,faa)]=tree;
connect(fa,tree,k^1);
pushup(fa);pushup(tree);
}
inline void splay(reg tr *tree){
reg tr *fa,*faa;
while(notroot(tree)){
fa=tree->fa;faa=fa->fa;
if(notroot(fa)) rotate(ident(tree,fa)^ident(fa,faa)?tree:fa);
rotate(tree);
}
}
inline void access(reg tr *x){
for(reg tr *lastx=null;x!=null;lastx=x,x=x->fa){
pushdown(x);
splay(x);
x->son[1]=lastx;pushup(x);
}
}
inline void makeroot(tr *x){
access(x);
splay(x);
x->tag^=1;
}
inline tr *findroot(tr *x){
access(x);splay(x);
pushdown(x);
while(x->son[0]!=null) x=x->son[0],pushdown(x);
splay(x);
return x;
}
inline int linked(tr *x,tr *y){
makeroot(x);
return findroot(y)==x;
}
inline void split(tr *x,tr *y){
makeroot(x);
access(y);splay(y);
}
inline void link(tr *x,tr *y){
makeroot(x);
if(findroot(y)!=x) x->fa=y;
}
inline void cut(tr *x,tr *y){
split(x,y);
x->fa=y->son[0]=null;
}
inline void init(){
null=&dizhi[0];
for(reg int i=1;i<=n;i++){
pos[i]=&dizhi[i];
dizhi[i].son[0]=dizhi[i].son[1]=dizhi[i].fa=null;
}
}
inline void creat(int i,int l){
pos[i]=&dizhi[i];
dizhi[i].son[0]=dizhi[i].son[1]=dizhi[i].fa=null;
dizhi[i].min=dizhi[i].thismin=i-n;
dizhi[i].sumlen=dizhi[i].len=l;
}
int main(){
n=read();m=read();
init();
tem[0]=2e9;
char c;int id,u,v,k;
while(m--){
c=getchar();
while(c!='f'&&c!='c'&&c!='m') c=getchar();
if(c=='f'){
id=read()+1+n;u=read()+1;v=read()+1;tem[id-n]=read();k=read();
creat(id,k);
if(linked(pos[u],pos[v])){
split(pos[u],pos[v]);
if(tem[pos[v]->min]>=tem[id-n]) continue;
int tmp=pos[v]->min;
cut(pos[tmp+n],pos[U[tmp]]);cut(pos[tmp+n],pos[V[tmp]]);
}
link(pos[id],pos[u]),link(pos[id],pos[v]);
U[id-n]=u;V[id-n]=v;
}
else if(c=='c'){
id=read()+1+n;k=read();
splay(pos[id]);
pos[id]->len=k;
pushup(pos[id]);
}
else{
u=read()+1;v=read()+1;
if(!linked(pos[u],pos[v])) puts("-1");
else{
split(pos[u],pos[v]);
printf("%d
",pos[v]->sumlen);
}
}
}
return 0;
}