樹鍊剖分，最小生成樹（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;
}