传送门：点击打开链接
题意：给一个图，有m条边n个点，如果对于一个最小生成树中要求必须包括第i条边，那么最小生成树的权值总和最小是多少
思路：求出最小生成树，然后对于m条边相当于m次查询，每次查询的时候，相当于求出在最小生成树中(u,v)路径上的边权最大值，那么新添加了一条边，就要把这条最大值的边删掉。所以题目转换成了，求路径上边权最大值。可以用LCA来做，也可以用树链剖分来维护。
LCA维护
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 2e5 + 5;
const int MS = 4e5 + 5;
const int M = 25;//n的log
const int INF = 0x3f3f3f3f;struct Edge {int u, v, nxt, cost, id;bool operator<(const Edge &P) const {return cost < P.cost;}
} E[MS], A[MX];
int rear, Head[MX];
void edge_init() {rear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v, int cost) {E[rear].u = u;E[rear].v = v;E[rear].cost = cost;E[rear].nxt = Head[u];Head[u] = rear++;
}LL mincost, ans[MX];
int n, m, P[MX];
int find(int x) {return P[x] == x ? x : (P[x] = find(P[x]));
}
void MST() {mincost = 0;f