CF1399E1 Weights Division (easy version) 题解

题目链接：CF1399E1 Weights Division (easy version)

题意：

给定一棵以 \(1\) 号点为根的带权有根树。

树是一个无环连通图。有根树有一个被称作根的特殊节点。在从根到节点 \(v\) 的路径上，最后一个不同于 \(v\) 的节点被称作节点 \(v\) 的父亲节点。以节点 \(v\) 为父亲的节点称为节点 \(v\) 的儿子节点。若一个节点没有任何儿子，则称它为叶子节点。带权树上的边带有权值。

定义一条路径的权值为这条路径上所有边的权值之和。特别地，一条从某个节点到它自己的路径权值为 \(0\)。

你可以进行一系列的操作，操作零次或多次。对于每次操作，你可以选择任意一条边，将其权值除以 \(2\)（向下取整）。更正式地说，在每次操作中，你可以选择一条边 \(i\)，使得这条边的权值 \(w_i\) 变成 \(\lfloor \frac{w_i}{2} \rfloor\)。

你的任务是找到最小操作数，以满足所有从根到叶子的路径的权值之和不超过 \(S\)。换句话说，如果设 \(w(i,j)\) 为从节点 \(i\) 到节点 \(j\) 的路径的权值，那么你需要使得 \(\sum_{v \in \mathtt{leaves}} w(\mathtt{root},v) \leq S\)，其中 \(\mathtt{leaves}\) 是所有叶子组成的集合。

你需要回答 \(t\) 组独立的数据。

输入格式：

输入第一行包含一个整数 \(t\;(1 \leq t \leq 2 \cdot 10^4)\)，表示数据组数。

接着输入 \(t\) 组数据。

每组数据的第一行包含两个整数 \(n\) 和 \(S~(2 \leq n \leq 10^5,1 \leq S \leq 10^{16})\)，分别表示树上节点数，和你需要满足的最大可能的权值和。

紧接着 \(n-1\) 行描述树上的边。边 \(i\) 会以三个整数 \(v_i,u_i\) 和 \(w_i~(1 \leq v_i,u_i \leq n,1 \leq w_i \leq 10^6)\) 进行描述，其中 \(v_i\) 和 \(u_i\) 是连接边 \(i\) 的两个端点，\(w_i\) 是这条边的权值。

保证所有 \(n\) 的和不超过 \(10^5\;(\sum n \leq 10^5)\)。

输出格式：

对于每组数据，输出一行答案，表示能满足所有从根到叶子的路径的权值之和不超过 \(S\) 的最小操作数。

这道题告诉我们一个道理，我们贪心选择不是基于某个值域贪心，而是基于最大化利益贪心。

说人话就是，这题不是按「边权 \(\times\) 经过次数」贪心，而是按照「 \(\left(\texttt{边权}-\left\lfloor\texttt{边权} / 2\right\rfloor\right) \times \texttt{经过次数}\) 」贪心。

要搞清楚到底为什么贪心，不是盲猜什么最大值什么的。

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

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,S,cnt,res,sum,pos=1,head[N],s[N],w[N];
struct Edge { int u,v,w,next; } e[N * 2];
struct Pii { int id,val; };
bool operator < (Pii a, Pii b)
{ return (a.val - a.val / 2) * s[a.id] < (b.val - b.val / 2) * s[b.id]; }
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
priority_queue<Pii> q;
int dfs(int u,int fa)
{
    int c = 0, ok = 0;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        ok = 1; c += dfs(v,u); w[v] = e[i].w;
    }
    return s[u] = ok ? c : 1;
}
void clear()
{
    pos = 1; while(!q.empty()) q.pop();
    for(int i=1; i<=n; i++) head[i] = s[i] = w[i] = 0;
}
void solve()
{
    clear(); cin >> n >> S; res = sum = 0;
    for(int i=1,u,v,w; i<n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    dfs(1,0);
    for(int i=2; i<=n; i++){ q.push({i, w[i]}); sum += w[i] * s[i]; }
    for(int x,y; sum > S; )
    {
        tie(x,y) = tie(q.top().id, q.top().val); q.pop();
        ++res; sum -= (y - (y / 2)) * s[x]; q.push({x, y / 2});
    }
    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 _Q; cin >> _Q; while(_Q--) solve();
    return 0;
}