codeforces 733F (樹鍊剖分 RMQ)

題目連結：點選這裡

題意：給出一個圖，每條邊有權值和花費c，每次花費ｃ能使的權值-1。給出一個預算，求減完權值後的一個最小生成樹。

觀察到最優的政策必然是隻減少一條邊的權值。于是首先先将初始權值做一次最小生成樹。然後枚舉所有的邊，如果這條邊是生成樹的邊，求出預算都花在這條邊上的結果；如果非樹邊，就在這條邊兩個點到他們的ＬＣＡ路徑上求出樹邊的最大值，這個最大值用輕重鍊剖分維護，（也可以往上倍增）樹鍊上無修改的最大值可以用ＲＭＱ維護，然後求出扣掉這個最大樹邊，加進去這條邊的最終結果。中間過程維護一下最小值。

#include <bits/stdc++.h>
using namespace std;
#define Clear(x,y) memset (x,y,sizeof(x));
#define maxn 200005
#define maxm maxn<<1

int n, m;
long long w[maxn], c[maxn], S;
struct E {
    int u, v, id;
    bool operator < (const E &a) const {
        return w[id] < w[a.id];
    }
}e[maxn];
bool in_mst[maxn];//每條邊在不在ｍｓｔ中

struct node {
    int v, next, id;
}edge[maxm];
int head[maxn], cnt;
int top[maxn], fa[maxn], deep[maxn], num[maxn], p[maxn], fp[maxn];
int son[maxn], pos;
long long MST;

void add_edge (int u, int v, int id) {
    edge[cnt].id = id;
    edge[cnt].v = v, edge[cnt].next = head[u], head[u] = cnt++;
}

int Find (int x) {return fa[x] == x ? fa[x] : fa[x] = Find (fa[x]);}
void init () {
    MST = ;
    Clear (in_mst, );
    Clear (head, -);
    cnt = ;
    for (int i = ; i <= n; i++) fa[i] = i;
    for (int i = ; i <= m; i++) {// cout << e[i].id << " ";
        int p1 = Find (e[i].u), p2 = Find (e[i].v);
        if (p1 != p2) {
            fa[p1] = p2;
            MST += w[e[i].id];
            in_mst[e[i].id] = ;
            add_edge (e[i].u, e[i].v, e[i].id);
            add_edge (e[i].v, e[i].u, e[i].id);
        }
    } //cout << endl;
    Clear (son, -);
    pos = ;
    //for (int i = 1; i <= m; i++) if (in_mst[i]) cout << i << " "; cout << endl;
    //cout << MST << endl;
}

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

#define pii pair<long long, int>
#define mp make_pair
pii dp[maxn][];
pii min (pii a, pii b) {
    return a < b ? a : b;
}
pii max (pii a, pii b) {
    return a < b ? b : a;
}

void getpos (int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -) return ;
    getpos (son[u], sp);
    for (int i = head[u]; i != -; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa[u] || v == son[u]) continue;
        getpos (v, v);
    }
}

void dfs2 (int u) {
    for (int i = head[u]; i != -; i = edge[i].next) {
        int v = edge[i].v; if (v == fa[u]) continue;
        dp[p[v]][] = mp (w[edge[i].id], edge[i].id);
        dfs2 (v);
    }
}

void rmq_init () {
    dfs2 ();
    for (int j = ; (<<j) <= n; j++) {
        for (int i = ; i+(<<j)- < n; i++) {
            dp[i][j] = max (dp[i][j-], dp[i+(<<(j-))][j-]);
        }
    }
}

pii rmq (int l, int r) {
    int k = ;
    while ((<<(k+)) <= r-l+) k++;
    return max (dp[l][k], dp[r-(<<k)+][k]);
}

pii query (int u, int v) {
    int f1 = top[u], f2 = top[v];
    pii tmp = mp (, );
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap (u, v);
            swap (f1, f2);
        }
        tmp = max (tmp, rmq (p[f1], p[u]));
        u = fa[f1]; f1 = top[u];
    }
    if (u == v) return tmp;
    if (deep[u] > deep[v]) swap (u, v);
    return max (tmp, rmq (p[son[u]], p[v]));
}

void solve () {
    dfs1 (, , );
    getpos (, );
    rmq_init ();
    long long ans = ; int pos = -, del = -;
    for (int i = ; i <= m; i++) {
        long long tmp;
        if (in_mst[e[i].id]) {
            tmp = MST-S/c[e[i].id];
            if (tmp < ans) {
                ans = tmp;
                pos = e[i].id;
            }
        }
        else {
            pii Min = query (e[i].u, e[i].v);
            tmp = MST-w[Min.second]+w[e[i].id]-S/c[e[i].id];
            if (tmp < ans) {
                ans = tmp;
                pos = e[i].id;
                del = Min.second;
            }
        }
    }
    cout << ans << "\n";
    for (int i = ; i <= m; i++) if (in_mst[i] || i == pos) {
        if (i == del) continue;
        cout << i << " ";
        if (i == pos) cout << w[i]-S/c[i] << "\n";
        else cout << w[i] << "\n";
    }
}

int main () {
    //freopen ("more.in", "r", stdin);
    ios::sync_with_stdio ();
    cin >> n >> m;
    for (int i = ; i <= m; i++) cin >> w[i];
    for (int i = ; i <= m; i++) cin >> c[i];
    for (int i = ; i <= m; i++) {
        cin >> e[i].u >> e[i].v;
        e[i].id = i;
    }
    cin >> S;
    sort (e+, e++m);
    init ();
    solve ();
    return ;
}