CF1399E2 Weights Division (hard version) 题解

题目链接：CF1399E2 Weights Division (hard version)

题意：

给出一个结点数量为 \(n\) 的边带权的有根树，树的根结点为 \(1\)。你可以进行以下操作。

选定任意一条权值为 \(w_i\) 的边，使 \(w_i \gets \lfloor \frac{w_i}{2} \rfloor\)，花费为 \(c_i\) 且 \(c_i \in \{1, 2\}\)。

定义 \(w(i,j)\) 为结点 \(i\) 到结点 \(j\) 的路径边权和。

对于每组测试数据，你需要回答最小的花费，使得 \(\sum\limits_{v\in \mathtt{leaves}}w(\mathtt{root},v)\leq S\)

其中 \(\mathtt{leaves}\) 为叶子结点编号的集合。

输入格式：

输入的第一行包含一个整数 \(t\) (\(1 \le t \le 2 \cdot 10^4\)) — 测试用例的数量。接下来是 \(t\) 个测试用例。

每个测试用例的第一行包含两个整数 \(n\) 和 \(S\) (\(2 \le n \le 10^5; 1 \le S \le 10^{16}\)) — 树中顶点的数量和你必须获得的最大可能权重总和。接下来的 \(n-1\) 行描述树的边。第 \(i\) 条边由四个整数 \(v_i\), \(u_i\), \(w_i\), 和 \(c_i\) 描述 (\(1 \le v_i, u_i \le n; 1 \le w_i \le 10^6; 1 \le c_i \le 2\))，其中 \(v_i\) 和 \(u_i\) 是边 \(i\) 连接的顶点，\(w_i\) 是该边的权重，\(c_i\) 是该边的成本。

保证 \(n\) 的总和不超过 \(10^5\) (\(\sum n \le 10^5\))。

输出格式：

对于每个测试用例，输出答案：使从根到每个叶子的路径上权重总和至多为 \(S\) 所需的最小总成本。

通过 CF1399E1 的铺垫，本题就较为简单了。（是的，这篇文章已经迟到了17个月，~~好在它终究来了~~）

仍然考虑贪心，但是因为这里有两种边权不能直接贪心

我们可以预处理出只用花费为 \(1\) 的修改，用任意次的花费（贪心即可），同理可算出只用 \(2\) 的情况。

然后枚举我们要用多少次 \(2\) 的修改，更新一下答案。

关于这道题的题解为什么现在才写完，很大程度上是因为这道题的代码比较复杂。

时间复杂度 \(\mathcal{O}(n \log nW )\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define Fi first
#define Se second
#define N ((int)(1e5 + 15))
#define M ((int)(2e6 + 15))

int n, S, w[N], c[N], val[N], cnt1, cnt2, A[M], B[M];
struct node { int x, y; } ;
int f(node a) { return (a.x - a.x / 2) * a.y; }
bool operator<(node a, node b) { return f(a) < f(b); }
vector<node> vec[N]; priority_queue<node> q;
int dfs(int u, int fa)
{
    int sz = 1, t = 0;
    for(auto i : vec[u])
    {
        int v = i.x; if(v == fa) continue;
        t = 1; val[i.y] = dfs(v, u); sz += val[i.y];
    }
    return sz - t;
}
void clear()
{
    cnt1 = cnt2 = 0;
    while(!q.empty()) q.pop();
    for(int i = 1; i <= n; i++)  { val[i] = 0; vec[i].clear(); }
}
void solve()
{
    cin >> n >> S; clear();
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v >> w[i] >> c[i];
        vec[u].push_back({v, i});
        vec[v].push_back({u, i});
    }
    dfs(1, 0); int now = 0, sum = 0;
    for(int i = 1; i < n; i++)
        if(c[i] == 1) { now += w[i] * val[i]; q.push({w[i], val[i]}); }
    S -= now;
    while(now)
    {
        auto u = q.top(); q.pop(); sum += f(u);
        A[++cnt1] = f(u); now -= f(u); u.x /= 2; q.push(u);
    }
    now = 0; while(!q.empty()) q.pop();
    for(int i = 1; i < n; i++)
        if(c[i] == 2) { now += w[i] * val[i]; q.push({w[i], val[i]}); }
    S -= now;
    while(now)
    {
        auto u = q.top(); q.pop();
        B[++cnt2] = f(u); now -= f(u); u.x /= 2; q.push(u);
    }
    while(!q.empty()) q.pop();
    if((S = -S) <= 0) { return cout << "0\n", void(0); }
    int res = cnt1 + cnt2 * 2 + 1;
    for(int i = 0; i <= cnt2; i++)
    {
        sum += B[i];
        while(cnt1 && sum - A[cnt1] >= S) { sum -= A[cnt1], --cnt1; }
        if(sum >= S) down(res, cnt1 + i * 2);
    }
    if(res == cnt1 + cnt2 * 2 + 1) cout << "-1\n"; else cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}