题解归档 - cf104114M

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114M
• 本地来源：problems/cf104114M/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/M
• 原始标题：cf104114M - Mousetrap

思路

cf104114M - Mousetrap

Only chambers on the simple path from 1 to n can help. Adding cheese outside the escape path only increases some denominator or is never smelled.

For an edge on the path u -> v, let

• A = c[v], the current cheese at the path child;
• B = sum c[w] over the other unvisited neighbours of u.

If we add y cheese to v, this factor of the escape probability becomes

(A+y)/(A+y+B).

The same added cheese affects no other factor, because the mouse chooses based on cheese in neighbouring chambers, not the current chamber. Therefore we need distribute at most x integer units among independent concave functions.

The marginal score of giving the next unit when current value is z=A+y is monotone decreasing:

log((z+1)/(z)) - log((z+B+1)/(z+B)),

equivalently ordered by the rational value

B / (z * (z+B+1)).

Binary search a marginal threshold to get almost all allocations, then adjust with priority queues using exact __int128 rational comparisons. If every B=0, the escape probability is already 1, so output all zeroes.

代码

来源：problems/cf104114M/solution.cpp

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

struct Item{
    int v;
    ll c,b;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll x;
    cin>>n>>x;
    vector<ll> c(n+1);
    for(int i=1;i<=n;i++) cin>>c[i];
    vector<vector<int>> g(n+1);
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> par(n+1,-1);
    queue<int> q;
    q.push(1);
    par[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v:g[u]){
            if(par[v]!=-1) continue;
            par[v]=u;
            q.push(v);
        }
    }
    vector<int> path;
    for(int v=n;v;v=par[v]) path.push_back(v);
    reverse(path.begin(),path.end());

    vector<Item> it;
    for(int i=0;i+1<(int)path.size();i++){
        int u=path[i],nxt=path[i+1],pre=(i?path[i-1]:0);
        ll side=0;
        for(int v:g[u]){
            if(v!=pre&&v!=nxt) side+=c[v];
        }
        if(side>0) it.push_back({nxt,c[nxt],side});
    }

    vector<ll> add(n+1,0);
    if(it.empty()||x==0){
        for(int i=1;i<=n;i++){
            if(i>1) cout<<" ";
            cout<<0;
        }
        cout<<"\n";
        return 0;
    }

    int k=(int)it.size();
    vector<ll> take(k,0);

    auto cnt_ge=[&](long double tau)->long long{
        if(tau<=0) return x;
        long long tot=0;
        for(auto &e:it){
            long double B=e.b;
            long double C=e.c;
            long double val=B/tau;
            long double disc=(B+1)*(B+1)+4*val;
            long double z=floor((-(B+1)+sqrt(disc))/2.0L+1e-12L);
            ll zz=(ll)z;
            while((long double)e.b/((long double)(zz+1)*(zz+1+e.b+1))>=tau) zz++;
            while(zz>=e.c&&(long double)e.b/((long double)zz*(zz+e.b+1))<tau) zz--;
            if(zz>=e.c){
                tot+=zz-e.c+1;
                if(tot>=x) return x;
            }
        }
        return tot;
    };

    long double lo=0,hi=1;
    for(int rep=0;rep<120;rep++){
        long double mid=(lo+hi)/2;
        if(cnt_ge(mid)>=x) lo=mid;
        else hi=mid;
    }

    ll total=0;
    for(int i=0;i<k;i++){
        auto &e=it[i];
        long double B=e.b;
        long double val=B/lo;
        long double disc=(B+1)*(B+1)+4*val;
        long double z=floor((-(B+1)+sqrt(disc))/2.0L+1e-12L);
        ll zz=(ll)z;
        while((long double)e.b/((long double)(zz+1)*(zz+1+e.b+1))>=lo) zz++;
        while(zz>=e.c&&(long double)e.b/((long double)zz*(zz+e.b+1))<lo) zz--;
        if(zz>=e.c) take[i]=zz-e.c+1;
        total+=take[i];
    }

    auto den=[&](int i,ll z)->i128{
        return (i128)z*(z+it[i].b+1);
    };
    auto less_score=[&](pair<int,ll>a,pair<int,ll>b)->bool{
        i128 lhs=(i128)it[a.first].b*den(b.first,b.second);
        i128 rhs=(i128)it[b.first].b*den(a.first,a.second);
        if(lhs!=rhs) return lhs<rhs;
        return a.first<b.first;
    };

    struct CmpMin{
        decltype(less_score)*cmp;
        bool operator()(pair<int,ll>a,pair<int,ll>b)const{
            return (*cmp)(b,a);
        }
    };
    struct CmpMax{
        decltype(less_score)*cmp;
        bool operator()(pair<int,ll>a,pair<int,ll>b)const{
            return (*cmp)(a,b);
        }
    };

    priority_queue<pair<int,ll>,vector<pair<int,ll>>,CmpMin> rem((CmpMin{&less_score}));
    for(int i=0;i<k;i++){
        if(take[i]) rem.push({i,it[i].c+take[i]-1});
    }
    while(total>x&&!rem.empty()){
        auto [i,z]=rem.top();
        rem.pop();
        if(take[i]==0||z!=it[i].c+take[i]-1) continue;
        take[i]--;
        total--;
        if(take[i]) rem.push({i,it[i].c+take[i]-1});
    }

    priority_queue<pair<int,ll>,vector<pair<int,ll>>,CmpMax> ins((CmpMax{&less_score}));
    for(int i=0;i<k;i++) ins.push({i,it[i].c+take[i]});
    while(total<x&&!ins.empty()){
        auto [i,z]=ins.top();
        ins.pop();
        if(z!=it[i].c+take[i]) continue;
        take[i]++;
        total++;
        ins.push({i,it[i].c+take[i]});
    }

    for(int i=0;i<k;i++) add[it[i].v]=take[i];
    for(int i=1;i<=n;i++){
        if(i>1) cout<<" ";
        cout<<add[i];
    }
    cout<<"\n";
    return 0;
}