Codeforces Round #661 (Div. 3) E2. Weights Division (hard version)

发表于 分类于

链接

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

题意

树形图上，每次选一条边使其边权 $w$ 变为$\lfloor\frac{w}{2}\rfloor$

每条边的花费为 $1$ 或 $2$

求让$\sum\limits_{v\in leaves}{w(root,v)}\le s$的最小花费

思路

DFS 求出每条边经过多少路径并不断对其操作记录每次对答案的贡献

用两个数组分别存 花费 $1$ 和花费 $2$ 的贡献，从大到小排序，求前缀和，因为某条边的贡献前一次操作必大于后一次操作，所以排序后是合法的

从左向右遍历花费 $1$ 的数组，并从右向左枚举花费 $2$ 的数组找到最小的满足要求的下标，取最小值为答案

因为数组可能为空，或者可能最小值为只取一种花费的情况，所以可以在数组开头加个 $0$，表示该种花费不操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pii;
typedef vector<int> vi;
//head
const int N=1e5+5;
int n,s,sum;
struct E {
    int v,w,c;
    E(){}
    E(int v,int w,int c):v(v),w(w),c(c){}
};
vector<E> G[N];
vi p,q;
bool cmp(int a,int b) {
    return a>b;
}
int dfs(int u,int fa,int w,int c) {
    int sz=0;
    for(auto x:G[u]) {
        int v=x.v,w=x.w,c=x.c;
        if(v==fa) continue;
        sz+=dfs(v,u,w,c);
    }
    if(!sz) sz=1;
    sum+=sz*w;
    if(c==1) while(w*sz-w/2*sz) p.pb(w*sz-w/2*sz),w/=2;
    else while(w*sz-w/2*sz) q.pb(w*sz-w/2*sz),w/=2;
    return sz;
}
void solve() {
    p.clear(),q.clear();
    p.pb(0),q.pb(0);
    dfs(1,0,0,0);
    sort(p.begin()+1,p.end(),cmp);
    sort(q.begin()+1,q.end(),cmp);
    for(int i=2;i<(int)p.size();i++) p[i]+=p[i-1];
    for(int i=2;i<(int)q.size();i++) q[i]+=q[i-1];
    int res=0x3f3f3f3f;
    sum-=s;
    for(int i=0,j=q.size()-1;i<(int)p.size();i++) {
        bool f=false;
        while(j>=0&&p[i]+q[j]>=sum) j--,f=true;
        if(f) j++;
        if(p[i]+q[j]>=sum) res=min(res,i+j*2);
    }
    printf("%lld\n",res);
}
signed main() {
    int T;
    scanf("%lld",&T);
    while(T--) {
        scanf("%lld%lld",&n,&s);
        sum=0;
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<n;i++) {
            int u,v,w,c;
            scanf("%lld%lld%lld%lld",&u,&v,&w,&c);
            G[u].pb(E(v,w,c));
            G[v].pb(E(u,w,c));
        }
        solve();
    }
    return 0;
}