Cod sursă (job #624859)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

int n,m,k;
int x,y,c;
vector <pair <int,int>> g[10005],tree[10005];
int t[10005];
int par[10005],wpar[10005],whsub[10005],csub[10005];

struct edge
{
    int x,y,c;
    bool operator < (const edge alta) const
    {
        return c<alta.c;
    }
} a[100005];

int root(int x)
{
    if(t[x]!=x)
        t[x]=root(t[x]);
    return t[x];
}

void unire(int x,int y)
{
    x=root(x);
    y=root(y);
    t[y]=x;
}

int cnt;

void dfs(int u,int p)
{
    if(u!=1)
    {
        whsub[u]=cnt;
        if(par[u]==1)
            csub[cnt]=wpar[u];
    }
    for(auto e:tree[u])
    {
        if(e.first!=p)
        {
            if(u==1)
                cnt++;
            par[e.first]=u;
            wpar[e.first]=e.second;
            dfs(e.first,u);
        }
    }
}

int f(int x,int y)
{
    int res=0;
    if(y==1)
    {
        res+=csub[whsub[x]];
        res-=c;
    }
    else
    {
        res+=wpar[y];
        res-=c;
    }
    return res;
}

int main()
{
    fin>>n>>m>>k;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        a[i]={x,y,c};
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
    for(int i=1; i<=n; i++)
        t[i]=i;
    sort(a+1,a+m+1);
    int sum=0;
    for(int i=1; i<=m; i++)
    {
        x=a[i].x;
        y=a[i].y;
        c=a[i].c;
        if(root(x)!=root(y))
        {
            unire(x,y);
            sum+=c;
            tree[x].push_back(make_pair(y,c));
            tree[y].push_back(make_pair(x,c));
        }
    }
    dfs(1,0);
    fout<<sum<<"\n";
    for(int i=1; i<=k; i++)
    {
        fin>>x>>y>>c;
        if(x==y)
        {
            fout<<sum<<"\n";
            continue;
        }
        int a=f(x,y),b=f(y,x);
        if(a>b && a>0)
        {
            wpar[y]=c;
            par[y]=x;
            sum-=a;
        }
        else if(b>=a && b>0)
        {
            wpar[x]=c;
            par[x]=y;
            sum-=b;
        }
        fout<<sum<<"\n";
    }
    return 0;
}