1399-E2 题目大意

给定一棵\(n\)个节点的树，边带权，根节点为\(1\)。再给定一个整数\(S\)，你可以执行以下操作：

• 选择一条权值为\(w_i\)的边，令\(w_i\rightarrow \lfloor \frac{w_i}{2} \rfloor\)。

你可以执行任意次操作，使得\(\sum_{x∈leaves}sum(1,x)\)不大于\(S\)，其中\(sum(1,x)\)表示\(x\)到根节点的路径上的边权和。

Solution

一遍\(dfs\)求出各个边对答案的贡献，接下来依次执行操作，直到边权和小于等于\(S\)。

每次操作应当选取能够减少贡献最大的边，可以用优先队列来选取要操作的边。对于每个边在优先队列中的\(key\)应当是\((w_i-\lfloor \frac{w_i}{2} \rfloor)*cnt\)，\(cnt\)为该边对答案的贡献次数。操作完后还需把边权减半重新加入优先队列中。

每个边最多经过\(logU\)次操作就会变为\(0\)，这里的时间复杂度为\(O(nlognlogU)\)。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

void solve(){
    int n;
    ll S;
    cin>>n>>S;
    vector<vector<pair<int,int>>> e(n);
    for(int i=1;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        --x,--y;
        e[x].push_back({y,w});
        e[y].push_back({x,w});
    }
    ll cost=0;
    vector<int> sz(n);
    priority_queue<tuple<ll,int,int>> q;
    function<void(int,int)> dfs=[&](int x,int fa){
        if(e[x].size()==1&&e[x][0].first==fa){
            sz[x]=1;
            return;
        }
        for(auto [y,w]:e[x]){
            if(y==fa) continue;
            dfs(y,x);
            sz[x]+=sz[y];
            cost+=1LL*w*sz[y];
            q.push({1LL*(w-w/2)*sz[y],w/2,sz[y]});
        }
    };
    dfs(0,-1);
    int ans=0;
    while(cost>S){
        auto [d,w,c]=q.top();
        q.pop();
        cost-=d;
        q.push({1LL*(w-w/2)*c,w/2,c});
        ans++;
    }
    cout<<ans<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}