题目链接：UOJ 274
虽然小 R 住的宿舍楼早已来了暖气，但是由于某些原因，宿舍楼中的某些窗户仍然开着（例如厕所的窗户），这就使得宿舍楼中有一些路上的温度还是很低。
小 R 的宿舍楼中有 $n$ 个地点和一些路，一条路连接了两个地点，小 R 可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始，小 R 还不熟悉宿舍楼中的任何一条路，所以他会慢慢地发现这些路，他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。
小 R 需要在宿舍楼中活动，每次他都需要从一个地点到达另一个地点。小 R 希望每次活动时经过一条最温暖的路径，最温暖的路径的定义为，将路径上各条路的温度从小到大排序后字典序最大。即温度最低的路温度尽量高，在满足该条件的情况下，温度第二低的路温度尽量高，以此类推。小 R 不经过重复的路。由于每条路的温度互不相同，因此只存在一条最温暖的路径。
对于小 R 的每次活动，你需要求出小 R 需要走过的路径总长度。如果小 R 通过当前发现的路不能完成这次活动，则输出 $-1$。
注意本题中的字典序与传统意义上的字典序定义有所不同，对于两个序列 $a,b(a\ne b)$，若 $a$ 是 $b$ 的前缀则 $a$ 的字典序较大，同时可以推出空串的字典序最大。
一共有 $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$（保证在当前时间点这条边存在）。
数据范围：$1\le n\le 10^5$，$1\le m\le 3\times 10^5$，$0\le t\le 10^9$，$0\le l\le 10^4$。
Solution
我们用 $\text{LCT}$ 维护子树内最小温度的边，每次加边时如果没有连通则直接加入；否则和目前链 $(u,v)$ 上的最小温度比较，如果 $t$ 大于最小温度则断开最小温度的边，加入 $(u,v)$。查询时直接查链的长度即可。
注意：本题 $\text{hack}$ 数据卡常，因此不要使用 $\text{findroot}$ 查询连通性；而使用并查集！
时间复杂度：$\mathcal O(m\log n)$。
Code
#include <cstdio>
#include <algorithm>
const int N = 4e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m, fr[N], to[N], tem[N], len[N], f[N];
struct Node;
Node *null;
struct Node {
Node *ch[2], *fa;
int sum, mn, idx;
bool rev;
Node(int _idx = 0) {
ch[0] = ch[1] = fa = null;
sum = mn = rev = 0, idx = _idx;
}
bool get() {
return fa->ch[1] == this;
}
bool isroot() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void reverse() {
rev ^= 1, std::swap(ch[0], ch[1]);
}
void pushup() {
mn = idx;
if (ch[0] != null && tem[ch[0]->mn] < tem[mn]) mn = ch[0]->mn;
if (ch[1] != null && tem[ch[1]->mn] < tem[mn]) mn = ch[1]->mn;
sum = ch[0]->sum + ch[1]->sum + len[idx];
}
void pushdown() {
if (rev) {
ch[0]->reverse();
ch[1]->reverse();
rev = 0;
}
}
} *a[N];
struct LCT {
LCT(int n) {
null = new Node();
null->ch[0] = null->ch[1] = null->fa = null;
for (int i = 1; i <= n; i++) {
a[i] = new Node(i);
}
}
void pushtag(Node *x) {
if(!x->isroot()) pushtag(x->fa);
x->pushdown();
}
void rotate(Node *x) {
Node *y = x->fa, *z = y->fa;
int k = x->get();
!y->isroot() && (z->ch[y->get()] = x), x->fa = z;
y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
x->ch[!k] = y, y->fa = x;
y->pushup();
}
void splay(Node *x) {
pushtag(x);
while (!x->isroot()) {
Node *y = x->fa;
if (!y->isroot()) {
rotate(x->get() == y->get() ? y : x);
}
rotate(x);
}
x->pushup();
}
void access(Node *x) {
for (Node *y = null; x != null; x = (y = x)->fa) {
splay(x), x->ch[1] = y, x->pushup();
}
}
void makeroot(Node *x) {
access(x), splay(x), x->reverse();
}
Node *findroot(Node *x) {
access(x), splay(x);
x->pushdown();
while (x->ch[0] != null) {
(x = x->ch[0])->pushdown();
}
return x;
}
void split(Node *x, Node *y) {
makeroot(x), access(y), splay(y);
}
void link(Node *x, Node *y) {
makeroot(x);
if (findroot(y) != x) x->fa = y;
}
void cut(Node *x, Node *y) {
makeroot(x);
if (findroot(y) == x && x->fa == y && x->ch[1] == null) {
x->fa = y->ch[0] = null, y->pushup();
}
}
};
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
scanf("%d%d", &n, &m);
LCT lct(n + m);
for (int i = 1; i <= n; i++) {
tem[i] = INF, f[i] = i;
}
for (int i = 1; i <= m; i++) {
char s[10];
scanf("%s", s + 1);
if (s[1] == 'f') {
int id, u, v, t, l;
scanf("%d%d%d%d%d", &id, &u, &v, &t, &l), id += n + 1;
fr[id] = ++u, to[id] = ++v, tem[id] = t, len[id] = l;
if (find(u) == find(v)) {
lct.split(a[u], a[v]);
if (tem[a[v]->mn] < t) {
int k = a[v]->mn;
lct.cut(a[fr[k]], a[k]), lct.cut(a[to[k]], a[k]);
lct.link(a[u], a[id]), lct.link(a[v], a[id]);
}
} else {
lct.link(a[u], a[id]), lct.link(a[v], a[id]);
f[find(u)] = find(v);
}
} else if (s[1] == 'm') {
int u, v;
scanf("%d%d", &u, &v), u++, v++;
if (find(u) != find(v)) puts("-1");
else lct.split(a[u], a[v]), printf("%d\n", a[v]->sum);
} else {
int id, l;
scanf("%d%d", &id, &l), id += n + 1;
lct.splay(a[id]), len[id]=l, a[id]->pushup();
}
}
return 0;
}