yrfw

E1. Weights Division (easy version)

グラフプライオリティキュー変化量を考える貪欲法影響の大きさを考える

Codeforces Round #661 (Div. 3)

https://codeforces.com/contest/1399/problem/E1

問題

頂点1を根とする $n$ 頂点からなる木が与えられる。また、各辺には重み $w_i$ が付けられている。
操作を1度行うたび、任意の重みを $\lfloor \frac{w_i}{2} \rfloor$ に更新することが出来る。
根から葉へのパスの重みの総和を $s$ 以下にするには、最低で何回操作を行えば良いか求める。

解法

まず、根から葉に行くまでに通った各辺を通った回数を $cnt_i$ とし、各辺におけるスコアを $w_i \times c_i$ と定義する。
また、ある辺に対して操作を行ったときの変化量を $d=w_i \times c_i - \lfloor \frac{w_i}{2} \rfloor \times c_i$ とする。
プライオリティーキューに全ての辺の変化量を入れておき大きい順に $w_i$ を更新していけばよい。

各辺を通った回数は、dfsの帰りがけ順に計算していけばよい。
具体的には、各辺に番号 $id$ を振っておき、今見ている辺の親の辺 $pid$ に $cnt_{id}$ を加えていくとよい。

コード

https://codeforces.com/contest/1399/submission/94948972

using P = pair<ll, ll>;
vector<vector<P>> G;

vector<ll> cnt, w;

void dfs(int v, int pid) {
    if (G[v].size() == 1 && pid != -1) {
        cnt[pid] = 1;
    }

    for (auto nv : G[v]) {
        int id = nv.second;
        if (id == pid) continue;

        dfs(nv.first, id);
        if (pid != -1) cnt[pid] += cnt[id];
    }
}



ll get_diff(int id) {
    ll diff = w[id] * cnt[id] - (w[id] / 2) * cnt[id];
    return diff;
}


void solve() {
    ll n, s;
    cin >> n >> s;

    G.assign(n, vector<P>());
    cnt.assign(n - 1, 0);
    w.assign(n - 1, 0);

    rep(i, n - 1) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(P{ b, i });
        G[b].push_back(P{ a, i });
        w[i] = c;
    }

    dfs(0, -1);


    priority_queue<P> que;
    ll sum = 0;

    rep(i, n - 1) {
        ll diff = get_diff(i);
        que.push(P{ diff, i });
        sum += cnt[i] * w[i];
    }

    int ans = 0;

    while (sum > s) {
        int id = (que.top()).second;
        que.pop();
        sum -= get_diff(id);
        w[id] /= 2;
        que.push(P{ get_diff(id), id });
        ans++;
    }

    cout << ans << endl;
}


int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
}