题意：给定图，每条边都有一段存在时间。求每段时间的最小生成树。
解：动态MST什么毒瘤...洛谷上还是蓝题...
线段树分治 + lct维护最小生成树。
对时间开线段树，每条边的存在时间在上面会对应到logn个区间。
我们先把这些边加到线段树对应节点上，但是不在lct上面加。最后扫一遍线段树。
扫到一个节点的时候把当前节点上的边加入lct，同时记录做了什么操作。回溯的时候还原操作。
最小生成树的权值不用lct维护子树和，直接用一个变量，加边删边的时候跟着修改即可。
这样复杂度就是nlog2n的...虽然常数上天了。
注意一下就是，回溯操作的时候顺序必须严格倒序。否则会出现一些情况导致re。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 500010, lm = 32766; 7 8 int fa[N], s[N][2], large[N], p[N], top; 9 bool rev[N]; 10 LL val[N]; 11 12 inline void pushup(int x) { 13 large[x] = x; 14 if(s[x][0] && val[large[x]] < val[large[s[x][0]]]) { 15 large[x] = large[s[x][0]]; 16 } 17 if(s[x][1] && val[large[x]] < val[large[s[x][1]]]) { 18 large[x] = large[s[x][1]]; 19 } 20 return; 21 } 22 23 inline void pushdown(int x) { 24 if(rev[x]) { 25 std::swap(s[x][0], s[x][1]); 26 if(s[x][0]) { 27 rev[s[x][0]] ^= 1; 28 } 29 if(s[x][1]) { 30 rev[s[x][1]] ^= 1; 31 } 32 rev[x] = 0; 33 } 34 return; 35 } 36 37 inline bool no_root(int x) { 38 return (s[fa[x]][0] == x) || (s[fa[x]][1] == x); 39 } 40 41 inline void rotate(int x) { 42 int y = fa[x]; 43 int z = fa[y]; 44 bool f = (s[y][1] == x); 45 46 fa[x] = z; 47 if(no_root(y)) { 48 s[z][s[z][1] == y] = x; 49 } 50 s[y][f] = s[x][!f]; 51 if(s[x][!f]) { 52 fa[s[x][!f]] = y; 53 } 54 s[x][!f] = y; 55 fa[y] = x; 56 57 pushup(y); 58 return; 59 } 60 61 inline void splay(int x) { 62 int y = x; 63 p[++top] = y; 64 while(no_root(y)) { 65 y = fa[y]; 66 p[++top] = y; 67 } 68 while(top) { 69 pushdown(p[top]); 70 top--; 71 } 72 73 y = fa[x]; 74 int z = fa[y]; 75 while(no_root(x)) { 76 if(no_root(y)) { 77 (s[z][1] == y) ^ (s[y][1] == x) ? 78 rotate(x) : rotate(y); 79 } 80 rotate(x); 81 y = fa[x]; 82 z = fa[y]; 83 } 84 pushup(x); 85 return; 86 } 87 88 inline void access(int x) { 89 int y = 0; 90 while(x) { 91 splay(x); 92 s[x][1] = y; 93 pushup(x); 94 y = x; 95 //printf("fa %d = %d \n", x, fa[x]); 96 x = fa[x]; 97 } 98 return; 99 }100 101 inline void make_root(int x) {102 access(x);103 splay(x);104 rev[x] = 1;105 return;106 }107 108 inline int find_root(int x) {109 access(x);110 splay(x);111 while(s[x][0]) {112 x = s[x][0];113 pushdown(x);114 }115 return x;116 }117 118 inline void link(int x, int y) {119 //printf("link %d %d \n", x, y);120 make_root(x);121 fa[x] = y;122 return;123 }124 125 inline void cut(int x, int y) {126 //printf("cut %d %d \n", x, y);127 make_root(x);128 access(y);129 splay(y);130 s[y][0] = fa[x] = 0;131 pushup(y);132 return;133 }134 135 inline int getMax(int x, int y) {136 make_root(x);137 access(y);138 splay(y);139 return large[y];140 }141 // lct OVER142 143 struct Edge {144 int u, v;145 LL val;146 Edge(int x = 0, int y = 0, LL z = 0) {147 u = x;148 v = y;149 val = z;150 }151 }edge[N];152 153 struct Node {154 bool f; // 0 link 1 cut155 int x;156 Node(bool F = 0, int X = 0) {157 f = F;158 x = X;159 }160 };161 162 std::vector id[N];163 std::vector v[N];164 int n;165 LL Sum;166 167 void add(int L, int R, int v, int l, int r, int o) {168 if(L <= l && r <= R) {169 id[o].push_back(v);170 return;171 }172 int mid = (l + r) >> 1;173 if(L <= mid) {174 add(L, R, v, l, mid, o << 1);175 }176 if(mid < R) {177 add(L, R, v, mid + 1, r, o << 1 | 1);178 }179 return;180 }181 182 void solve(int l, int r, int o) {183 //printf("solve %d %d %d \n", l, r, o);184 for(int i = 0; i < id[o].size(); i++) {185 int t = id[o][i];186 int x = edge[t].u, y = edge[t].v;187 int p = getMax(x, y);188 if(val[p] < edge[t].val) {189 continue;190 }191 cut(edge[p].u, p);192 cut(edge[p].v, p);193 link(x, t);194 link(y, t);195 v[o].push_back(Node(1, p));196 v[o].push_back(Node(0, t)); // pay attention! this must be behind197 Sum -= val[p];198 Sum += val[t];199 //printf(" > push %d %d \n", t, p);200 }201 if(l == r) {202 printf("%lld\n", Sum + 1);203 }204 else {205 int mid = (l + r) >> 1;206 solve(l, mid, o << 1);207 solve(mid + 1, r, o << 1 | 1);208 }209 //printf(" -- solve %d %d %d \n", l, r, o);210 for(int i = v[o].size() - 1; i >= 0; i--) { // this must be sleep211 int t = v[o][i].x;212 if(v[o][i].f) {213 link(edge[t].u, t);214 link(edge[t].v, t);215 Sum += val[t];216 }217 else {218 cut(edge[t].u, t);219 cut(edge[t].v, t);220 Sum -= val[t];221 }222 //printf(" -- > pop %d \n", t);223 }224 v[o].clear();225 return;226 }227 228 int main() {229 230 scanf("%d", &n);231 LL z;232 for(int i = 1, x, y; i < n; i++) {233 scanf("%d%d%lld", &x, &y, &z);234 val[n + i] = z;235 link(x, n + i);236 link(n + i, y);237 edge[n + i].u = x;238 edge[n + i].v = y;239 edge[n + i].val = z;240 Sum += z;241 }242 int m;243 scanf("%d", &m);244 for(int i = 1, l, r; i <= m; i++) {245 int t = 2 * n + i;246 scanf("%d%d%lld%d%d", &edge[t].u, &edge[t].v, &edge[t].val, &l, &r);247 val[t] = edge[t].val;248 add(l, r, t, 1, lm, 1);249 }250 251 solve(1, lm, 1);252 253 return 0;254 }