树链剖分，最小生成树（Drivers Dissatisfaction，cf 733F）

首先要证明只修一条路是最优的。

只证两条路的情况，多条路同理。

假设同时修了两条路x，y。

如果这两条路最后都没有在最小生成树中，那么修理都白费了，不如把资金都投入到其中一条路上，这样这条路才有可能成为新生成树的一部分，从而减小总长度。

如果有且只有一条在最小生成树中，不妨设x在，y不在。那么花在y上的钱都白费了，不如全花在x上，让总长度进一步减小。或者把花在x上的钱花在y上，试图让y不白花。

如果两者都在最小生成树中，那么不如选择修理费更小的那一条，就能节约更多资金，从而使总长度更小。

证毕。

方法就是先对初始道路跑一遍最小生成树，求出总长度ans。然后枚举需要修理的那条道路，并将全部资金花在修理它上。得到一条新的道路。

如果这条道路已经在最小生成树中，那么把ans一减就是修理后的答案。

否则就需要对道路进行替换。

假设这条道路连接u，v。那么最先被替换的那条道路一定是u，v间长度最大的那条道路。然后ans一加一减就是修理后的答案。

想要快速求出树上u，v间的最长道路，需要用到树链剖分。然后线段树维护区间最大值以及最大值的编号即可。

代码

#include<bits/stdc++.h>
#define ls (now<<1)
#define rs (ls|1)
#define maxn 200010
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll INF=LONG_LONG_MAX>>2;
ll n,m,S;

/
//Edge
struct Edge
{
    ll to,val,next,id;
}edges[maxn<<1];
ll head[maxn],tot;
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}
void add(ll from,ll to,ll val,ll id)
{
    edges[tot].to=to;
    edges[tot].val=val;
    edges[tot].id=id;
    edges[tot].next=head[from];
    head[from]=tot++;
}
/

/
//Kruskal
ll u[maxn],v[maxn],w[maxn],c[maxn];
bool cmp(ll i,ll j){return w[i]<w[j];}
ll r[maxn],fa[maxn];
ll f(ll x){return fa[x]==x?x:fa[x]=f(fa[x]);}
bool vis[maxn];
ll Kruskal()
{
    ll ret=0;
    for(ll i=1;i<=n;i++) fa[i]=i;
    for(ll i=1;i<=m;i++) r[i]=i;
    sort(r+1,r+m+1,cmp);
    for(ll i=1;i<=m;i++)
    {
        ll e=r[i];
        ll x=f(u[e]),y=f(v[e]);
        if(x!=y)
        {
            add(u[e],v[e],w[e],e);
            add(v[e],u[e],w[e],e);
            fa[x]=y;
            vis[e]=true;
            ret+=w[e];
        }
    }
    return ret;
}
/

///
//线段树
pii tree[maxn<<2];

inline void up_data(ll now)
{
    tree[now]=max(tree[ls],tree[rs]);
}

void A(ll l,ll r,ll now,ll pos,ll val)
{
    if(l==r)
    {
        tree[now]=make_pair(val,pos);
        return;
    }
    ll m=(l+r)>>1;
    if(pos<=m) A(l,m,ls,pos,val);
    else A(m+1,r,rs,pos,val);
    up_data(now);
}

pii Q(ll l,ll r,ll now,ll ql,ll qr)
{
    if(ql<=l&&r<=qr) return tree[now];
    ll m=(l+r)>>1;
    pii ansl=make_pair(-INF,-INF),ansr=make_pair(-INF,-INF);
    if(qr>m) ansr=Q(m+1,r,rs,ql,qr);
    if(ql<=m) ansl=Q(l,m,ls,ql,qr);
    return max(ansl,ansr);
}


/
//树链剖分
ll siz[maxn],father[maxn],son[maxn],dep[maxn];

void dfs1(ll u,ll f,ll d)
{
    dep[u]=d;
    father[u]=f;
    siz[u]=1;
    son[u]=-1;
    for(ll i=head[u];~i;i=edges[i].next)
    {
        ll v=edges[i].to;
        if(v==f) continue;
        dfs1(v,u,d+1);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[v]>siz[son[u]])
            son[u]=v;
    }
}

ll tim,tid[maxn],top[maxn],rk[maxn];

void dfs2(ll u,ll tp)
{
    top[u]=tp;
    tid[u]=++tim;
    rk[tid[u]]=u;
    if(son[u]==-1) return;
    dfs2(son[u],tp);
    for(ll i=head[u];~i;i=edges[i].next)
    {
        ll v=edges[i].to;
        if(v==father[u]) continue;
        if(v==son[u])
        {
            A(1,n,1,tid[v]-1,edges[i].val);
            continue;
        }
        dfs2(v,v);
        A(1,n,1,tid[v]-1,edges[i].val);
    }
}
///

pii QQ(ll x,ll y)
{
    pii ret=make_pair(-INF,-INF);
    ll tpx=top[x],tpy=top[y];
    while(x!=y)
    {
        if(tpx!=tpy)
        {
            if(dep[tpx]>dep[tpy])
            {
                swap(x,y);
                swap(tpx,tpy);
            }
            ret=max(ret,Q(1,n,1,tid[tpy]-1,tid[y]-1));
            y=father[tpy];
            tpy=top[y];
        }
        else
        {
            if(dep[x]>dep[y])
            {
                swap(x,y);
                swap(tpx,tpy);
            }
            ret=max(ret,Q(1,n,1,tid[x],tid[y]-1));
            return ret;
        }
    }
    return ret;
}

void print(ll kjia,ll kjian)
{
    if(kjia==-1)
    {
        for(ll i=1;i<=m;i++)
            if(vis[i])
                printf("%I64d %I64d\n",i,w[i]);
    }
    else if(kjian==-1)
    {
        for(ll i=1;i<=m;i++)
            if(vis[i])
            {
                if(i==kjia)
                    printf("%I64d %I64d\n",i,w[i]-S/c[i]);
                else
                    printf("%I64d %I64d\n",i,w[i]);
            }
    }
    else
    {
        for(ll i=1;i<=m;i++)
        {
            if(i==kjia)
                printf("%I64d %I64d\n",i,w[i]-S/c[i]);
            else if(vis[i])
            {
                if(i==kjian) continue;
                printf("%I64d %I64d\n",i,w[i]);
            }
        }
    }
}

void solve(ll chu)
{
    ll ANS=chu;
    ll kjia=-1,kjian=-1;
    for(ll i=1;i<=m;i++)
        if(vis[i])
        {
            ll jian=S/c[i];
            if(ANS>chu-jian)
            {
                ANS=chu-jian;
                kjia=i;
                kjian=-1;
            }
        }
        else
        {
            pii MAX=QQ(u[i],v[i]);
            ll MIN=w[i]-S/c[i];
            ll XIN=chu-MAX.first+MIN;
            if(ANS>XIN)
            {
                ANS=XIN;
                kjia=i;
                kjian=rk[MAX.second+1];
                for(ll i=head[kjian];~i;i=edges[i].next)
                    if(edges[i].to==father[kjian])
                    {
                        kjian=edges[i].id;
                        break;
                    }
            }
        }
    printf("%I64d\n",ANS);
    print(kjia,kjian);
}

int main()
{
    init();
    scanf("%I64d %I64d",&n,&m);
    for(ll i=1;i<=m;i++)
        scanf("%I64d",&w[i]);
    for(ll i=1;i<=m;i++)
        scanf("%I64d",&c[i]);
    for(ll i=1;i<=m;i++)
        scanf("%I64d %I64d",&u[i],&v[i]);
    scanf("%I64d",&S);
    ll chu=Kruskal();
    dfs1(1,-1,1);
    dfs2(1,1);

    solve(chu);
    return 0;
}