Educational Codeforces Round 3 E. Minimum spanning tree for each edge 最小生成树+树链剖分+线段树

Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains n vertices and m edges.

For each edge (u, v) find the minimal possible weight of the spanning tree that contains the edge (u, v).

The weight of the spanning tree is the sum of weights of all edges included in spanning tree.

Input

First line contains two integers n and m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — the number of vertices and edges in graph.

Each of the next m lines contains three integers ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — the endpoints of the i-th edge and its weight.

Output

Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.

The edges are numbered from 1 to m in order of their appearing in input.

Examples

input

output

题意：给你n个点，m条边；

　　　第i条为必选边，求最小的生成树；

思路：先建好一颗最小生成树，如果边在生成树上，输出最小的即可；

　　　对于不在树上的如何求解：

　　　　　　原来建好的一棵树，再加入一条边，会使得形成一个环，去查找原来最小生成树中u到v最大的边权，最小生成树的权值减去最大的边权+当前的边权即使答案；

　　　无更新的区间最大值，可以用倍增的写法；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-4
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=2e5+10,M=1e6+10,inf=2147483647;
const ll INF=1e18+10,mod=2147493647;

///数组大小
struct edge
{
    int v,next;
} edge[N<<1];
int head[N<<1],edg,id,n;
/// 树链剖分

int fa[N],dep[N],son[N],siz[N]; // fa父亲，dep深度，son重儿子，siz以该点为子树的节点个数
int ran[N],top[N],tid[N],num[N];  // tid表示边的标号，top通过重边可以到达最上面的点，ran表示标记tid
void init()
{
    memset(son,-1,sizeof(son));
    memset(head,-1,sizeof(head));
    edg=0;
    id=0;
}

void add(int u,int v)
{
    edg++;
    edge[edg].v=v;
    edge[edg].next=head[u];
    head[u]=edg;
}

void dfs1(int u,int fath,int deep)
{
    fa[u]=fath;
    siz[u]=1;
    dep[u]=deep;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==fath)continue;
        dfs1(v,u,deep+1);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[v]>siz[son[u]])
            son[u]=v;
    }
}

void dfs2(int u,int tp)
{
    tid[u]=++id;
    top[u]=tp;
    ran[tid[u]]=u;
    if(son[u]==-1)return;
    dfs2(son[u],tp);
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==fa[u])continue;
        if(v!=son[u])
            dfs2(v,v);
    }
}

struct SGT
{
    int maxx[N<<2];
    void pushup(int pos)
    {
        maxx[pos]=max(maxx[pos<<1],maxx[pos<<1|1]);
    }
    void build(int l,int r,int pos)
    {
        if(l==r)
        {
            maxx[pos]=num[ran[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,pos<<1);
        build(mid+1,r,pos<<1|1);
        pushup(pos);
    }
    int query(int L,int R,int l,int r,int pos)
    {
        //cout<<L<<" "<<R<<" "<<l<<" "<<r<<endl;
        if(L<=l&&r<=R)return maxx[pos];
        int mid=(l+r)>>1;
        int ans=0;
        if(L<=mid)ans=max(ans,query(L,R,l,mid,pos<<1));
        if(R>mid) ans=max(ans,query(L,R,mid+1,r,pos<<1|1));
        return ans;
    }
}tree;

int up(int l,int r)
{
    int ans=0;
    while(top[l]!=top[r])
    {
        if(dep[top[l]]<dep[top[r]])swap(l,r);

        ans=max(ans,tree.query(tid[top[l]],tid[l],1,n,1));
        l=fa[top[l]];
    }

    if(dep[l]<dep[r])swap(l,r);
    if(l==r)return ans;
    ans=max(ans,tree.query(tid[son[r]],tid[l],1,n,1));
    return ans;
}
/// 克鲁斯卡尔
struct is
{
    int u,v,w,pos;
    operator <(const is &x)const
    {
        return w<x.w;
    }
}a[N];
int fafa[N],ans[N];
int Find(int x)
{
    return x==fafa[x]?x:fafa[x]=Find(fafa[x]);
}
ll out[N];
int main()
{
    init();
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w),a[i].pos=i;
    sort(a+1,a+1+m);
    ll minn=0;
    for(int i=1;i<=n;i++)
        fafa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=Find(a[i].u);
        int y=Find(a[i].v);
        if(x!=y)
        {
            add(a[i].u,a[i].v);
            add(a[i].v,a[i].u);
            fafa[x]=y;
            minn+=a[i].w;
            ans[i]=1;
        }
    }
    dfs1(1,-1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        if(ans[i])
        {
            if(fa[a[i].u]==a[i].v)
                num[a[i].u]=a[i].w;
            else
                num[a[i].v]=a[i].w;
        }
    }
    tree.build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        if(ans[i])out[a[i].pos]=minn;
        else
        {
            int x=up(a[i].u,a[i].v);
            out[a[i].pos]=minn-x+a[i].w;
        }
    }
    for(int i=1;i<=m;i++)
        printf("%lld
",out[i]);
    return 0;
}