题目链接：CF：Minimum spanning tree for each edge

题解：他要求我们求包含第ｉ条边的树的最小值，我们可以先跑一遍最小生成树，把最小生成树求出来，然后再进行加边删边处理。

当我们求出一个最小生成树后，假如再连边后肯定会形成一个自环，我们考虑在这个自环上删边（不是真删，而是输出减去其权值后的 ans ）。

比如在该图中，我们连接４,５两点，这三点会与其 LCA 成顶点形成自环 ，黄色那条边肯定是不能动的，要动的就是4-2和5-2这两条边，我们在处理 LCA 时变换一下，改为求解其从ｘ点到其 LCA 的所有连边上的最大值。我们考虑树上倍增，定义一数组 walth[i][j] 为从第i点开始向上跳 2^j 个点后第i点与第 2^j 点的连边中的最大值，然后用类似于求 LCA 的做法进行处理最终求得一条链边上的 max 值。

具体实现如下：

#include
#include 
#include
#include
#define Maxn 200005
using namespace std;
typedef long long ll;
//此部分用于树上倍增 
ll head[Maxn*2],lg[Maxn*4];
struct acb{
    ll next,to,w;
}tree[Maxn*2];
ll cut;
void Add(ll u,ll v,ll w){
    tree[++cut].to=v;
    tree[cut].next=head[u];
    tree[cut].w=w;
    head[u]=cut;
}
//
ll anc[Maxn][30],dept[Maxn],walth[Maxn][30];
ll n,m,fa[Maxn],top,len; 
bool bin[Maxn];
struct abc{
    ll u,v,w,ty,id;
}edge[Maxn*2];
bool cmp(abc x,abc y){
    return x.wdept[y]){
        maxx=max(maxx,walth[x][lg[dept[x]-dept[y]]-1]);//万一两点重合了，我们就只需要一条边上的最大值 
        //哪怕它们没重合，我们仍然需要这一点在往上跳的途中的最大值 
        x=anc[x][lg[dept[x]-dept[y]]-1];//注：顺序不要搞反了 
    }
    if(x==y) return maxx;
    for(int i=lg[dept[x]]-1;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            maxx=max(maxx,walth[x][i]); //两点没有重合，那就需要我们两边一起求取最大值 
            maxy=max(maxy,walth[y][i]);
            x=anc[x][i];
            y=anc[y][i];
            
        }
    } 
    maxx=max(walth[x][0],maxx);//注意，我们最后求到的x值是LCA的第一级儿子，还有一条边（ＬＣＡ与其第一级儿子的连边）没算 
    maxy=max(walth[y][0],maxy);
    return max(maxx,maxy);
}
bool check(ll x){
    if(bin[x]) return true;
    else return false;
} 
ll work(ll x){
    ll res=len;
    if(check(x))return res;//假如这一条边在最小生成树中，那么我们就不处理 
    else res+=edge[x].w; //否则，我们预先加上目标的那一条边的权值 
    ll u=edge[x].u;
    ll v=edge[x].v;
    ll lens=LCA(u,v);
    return res-lens;
}
//以上为代码实践 
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        fa[i]=i;
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        edge[i].id=i;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
    }
    len=kruskal();
    sort(edge+1,edge+m+1,rbq);//注：在求完最小生成树后一定要把数组纠正回来，因为题目要的是原装边加上并处理后的值 
    lg[1]=1;
    for(int i=2;i<=Maxn;i++)
        lg[i]=lg[i-1]+((1<