题意：给定图，每条边都有一段存在时间。求每段时间的最小生成树。
解：动态MST什么毒瘤...洛谷上还是蓝题...
线段树分治 + lct维护最小生成树。
对时间开线段树，每条边的存在时间在上面会对应到logn个区间。
我们先把这些边加到线段树对应节点上，但是不在lct上面加。最后扫一遍线段树。
扫到一个节点的时候把当前节点上的边加入lct，同时记录做了什么操作。回溯的时候还原操作。
最小生成树的权值不用lct维护子树和，直接用一个变量，加边删边的时候跟着修改即可。
这样复杂度就是nlog2n的...虽然常数上天了。
注意一下就是，回溯操作的时候顺序必须严格倒序。否则会出现一些情况导致re。
#include <cstdio>
#include <algorithm>
#include <vector> typedef long long LL;
const int N = , lm = ; int fa[N], s[N][], large[N], p[N], top;
bool rev[N];
LL val[N]; inline void pushup(int x) {
large[x] = x;
if(s[x][] && val[large[x]] < val[large[s[x][]]]) {
large[x] = large[s[x][]];
}
if(s[x][] && val[large[x]] < val[large[s[x][]]]) {
large[x] = large[s[x][]];
}
return;
} inline void pushdown(int x) {
if(rev[x]) {
std::swap(s[x][], s[x][]);
if(s[x][]) {
rev[s[x][]] ^= ;
}
if(s[x][]) {
rev[s[x][]] ^= ;
}
rev[x] = ;
}
return;
} inline bool no_root(int x) {
return (s[fa[x]][] == x) || (s[fa[x]][] == x);
} inline void rotate(int x) {
int y = fa[x];
int z = fa[y];
bool f = (s[y][] == x); fa[x] = z;
if(no_root(y)) {
s[z][s[z][] == y] = x;
}
s[y][f] = s[x][!f];
if(s[x][!f]) {
fa[s[x][!f]] = y;
}
s[x][!f] = y;
fa[y] = x; pushup(y);
return;
} inline void splay(int x) {
int y = x;
p[++top] = y;
while(no_root(y)) {
y = fa[y];
p[++top] = y;
}
while(top) {
pushdown(p[top]);
top--;
} y = fa[x];
int z = fa[y];
while(no_root(x)) {
if(no_root(y)) {
(s[z][] == y) ^ (s[y][] == x) ?
rotate(x) : rotate(y);
}
rotate(x);
y = fa[x];
z = fa[y];
}
pushup(x);
return;
} inline void access(int x) {
int y = ;
while(x) {
splay(x);
s[x][] = y;
pushup(x);
y = x;
//printf("fa %d = %d \n", x, fa[x]);
x = fa[x];
}
return;
} inline void make_root(int x) {
access(x);
splay(x);
rev[x] = ;
return;
} inline int find_root(int x) {
access(x);
splay(x);
while(s[x][]) {
x = s[x][];
pushdown(x);
}
return x;
} inline void link(int x, int y) {
//printf("link %d %d \n", x, y);
make_root(x);
fa[x] = y;
return;
} inline void cut(int x, int y) {
//printf("cut %d %d \n", x, y);
make_root(x);
access(y);
splay(y);
s[y][] = fa[x] = ;
pushup(y);
return;
} inline int getMax(int x, int y) {
make_root(x);
access(y);
splay(y);
return large[y];
}
// lct OVER struct Edge {
int u, v;
LL val;
Edge(int x = , int y = , LL z = ) {
u = x;
v = y;
val = z;
}
}edge[N]; struct Node {
bool f; // 0 link 1 cut
int x;
Node(bool F = , int X = ) {
f = F;
x = X;
}
}; std::vector<int> id[N];
std::vector<Node> v[N];
int n;
LL Sum; void add(int L, int R, int v, int l, int r, int o) {
if(L <= l && r <= R) {
id[o].push_back(v);
return;
}
int mid = (l + r) >> ;
if(L <= mid) {
add(L, R, v, l, mid, o << );
}
if(mid < R) {
add(L, R, v, mid + , r, o << | );
}
return;
} void solve(int l, int r, int o) {
//printf("solve %d %d %d \n", l, r, o);
for(int i = ; i < id[o].size(); i++) {
int t = id[o][i];
int x = edge[t].u, y = edge[t].v;
int p = getMax(x, y);
if(val[p] < edge[t].val) {
continue;
}
cut(edge[p].u, p);
cut(edge[p].v, p);
link(x, t);
link(y, t);
v[o].push_back(Node(, p));
v[o].push_back(Node(, t)); // pay attention! this must be behind
Sum -= val[p];
Sum += val[t];
//printf(" > push %d %d \n", t, p);
}
if(l == r) {
printf("%lld\n", Sum + );
}
else {
int mid = (l + r) >> ;
solve(l, mid, o << );
solve(mid + , r, o << | );
}
//printf(" -- solve %d %d %d \n", l, r, o);
for(int i = v[o].size() - ; i >= ; i--) { // this must be sleep
int t = v[o][i].x;
if(v[o][i].f) {
link(edge[t].u, t);
link(edge[t].v, t);
Sum += val[t];
}
else {
cut(edge[t].u, t);
cut(edge[t].v, t);
Sum -= val[t];
}
//printf(" -- > pop %d \n", t);
}
v[o].clear();
return;
} int main() { scanf("%d", &n);
LL z;
for(int i = , x, y; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
val[n + i] = z;
link(x, n + i);
link(n + i, y);
edge[n + i].u = x;
edge[n + i].v = y;
edge[n + i].val = z;
Sum += z;
}
int m;
scanf("%d", &m);
for(int i = , l, r; i <= m; i++) {
int t = * n + i;
scanf("%d%d%lld%d%d", &edge[t].u, &edge[t].v, &edge[t].val, &l, &r);
val[t] = edge[t].val;
add(l, r, t, , lm, );
} solve(, lm, ); return ;
}
AC代码