CF1399E2

· · 题解

这题是一道 2 \times 10^4 的多测题。

给你一棵树，树上每条边有对应的边权 w_i 和操作代价 c_i 。

让你对一些边进行操作，使它的边权变成 \lfloor \frac{w_i}{2} \rfloor 。

问你至少付出多少代价可以使所有叶子结点到根节点的路径权值和不超过 S 。

一条边显然可以被多个叶子结点计算答案。

n\leq 10^5 \sum n \leq 10^5

观察到只有 2 种代价 c_i 所以可以先预处理，再枚举操作多少代价为 2 的边。

预处理一种操作代价的边，就可以直接贪心了，毕竟操作代价相等。

可以使用 priority_queue 进行处理，贪心地选择操作产生贡献（答案变化）最大的边。

记第 i 条边在 d_i 个叶子结点到根结点的路径上，贡献就是 ( w_i - \lfloor \frac{w_i}{2} \rfloor ) \times d_i 。

对于一条边计算完答案要记得使 w_i = \lfloor \frac{w_i}{2} \rfloor ，在重新弹入优先队列。

因为选代价为 2 的边越多，需要选的代价为 1 的边数量单调递减，可以直接用双指针计算答案。

程序每组数据复杂度 O( \sum_{i = 1}^{n - 1}{ \log_{2}{w_i} } \times \log_{2}n) 。

计算答案的复杂度是 O( \sum_{i = 1}^{n - 1}{ \log_{2}{w_i} } ) 可以忽略不计。

代码如下 （非常的短)：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,l;
long long now,mst;
//xy在这里有两种意思
//在表示边是x是指向的点，y是边的编号
//在表示贡献时x是边的权值，y是边的覆盖叶节点数量
struct xy{int x,y;};
#define dv(a) (1ll*(a.x-(a.x>>1))*a.y)//计算贡献，如果更改一次则贡献是多少
bool operator < (xy a,xy b){return dv(a)<dv(b);}
xy ls;
long long sum;
int aa[101010],bb[101010],vs[101010];
long long a[2020202],as;
long long b[2020202],bs;
vector<xy>q[101010];
priority_queue<xy>p;
int dfs(int x,int fa){
    int siz=1,sf=0;
    for(register int i=0;i<q[x].size();++i){
        if(q[x][i].x==fa)continue;
        sf=1;
        vs[q[x][i].y]=dfs(q[x][i].x,x);
        siz+=vs[q[x][i].y];
    }
    return siz-sf;//返回叶节点个数
}
void doing(){
    cin>>n>>mst;
    for(register int i=1;i<=n;++i)q[i].clear();
    for(register int i=1;i<n;++i){
        scanf("%d %d %d %d",&s,&l,&aa[i],&bb[i]);
        q[s].push_back((xy){l,i});
        q[l].push_back((xy){s,i});
        vs[i]=0;
    }
    dfs(1,0);
    now=as=sum=0;
    //计算花费为1的所有边操作时能产生的贡献降序
    for(register int i=1;i<n;++i){
        if(bb[i]==2)continue;
        now+=1ll*aa[i]*vs[i];
        p.push((xy){aa[i],vs[i]});
    }
    mst-=now;
    while(now){
        ls=p.top();p.pop();
        sum+=dv(ls);
        a[++as]=dv(ls);
        now-=dv(ls);
        ls.x>>=1;
        p.push(ls);
    }
    while(p.size())p.pop();
    now=bs=0;
    //计算花费为2的所有边操作时能产生的贡献降序
    for(register int i=1;i<n;++i){
        if(bb[i]==1)continue;
        now+=1ll*aa[i]*vs[i];
        p.push((xy){aa[i],vs[i]});
    }
    mst-=now;
    while(now){
        ls=p.top();p.pop();
        b[++bs]=dv(ls);
        now-=dv(ls);
        ls.x>>=1;
        p.push(ls);
    }
    while(p.size())p.pop();
    mst=-mst;
    if(mst<=0ll){printf("0\n");return;}//一开始就符合要求，不用操作，但要判掉
    s=as+bs*2+1;
    //枚举要删多少花费为2的边，并得到答案
    for(register int i=0;i<=bs;++i){
        sum+=b[i];
        while(sum-a[as]>=mst && as)sum-=a[as--];
        if(sum>=mst && as+i*2<s)s=as+i*2;
    }
    if(s==as+bs*2+1)s=-1;
    printf("%d\n",s);
}
int main(){
    int t;
    cin>>t;
    while(t--)doing();
    return 0;
}