20221115_T3A+_贪心二分

题意

你在和 Yazid 做游戏。
Yazid 给了你一棵 \(n\) 个节点的树，并让你删除这棵树上的恰好 \(k\) 条边，使得整棵树被分成 \(k+1\) 个连通块。
你觉得太简单了，随便删 k 条边不就行了吗？
Yazid 想了一想，决定让你求出这些 \(k+1\) 个连通块的大小（一个连通块的大小指的是它包含的点数）。
你觉得太简单了，随便求一求不就求出来了吗？
Yazid 又想了一想，决定对你第一步的工作进行评价。对于连通块，Yazid 都会算出其罚分：设第 \(i\) 个连通块的大小为 \(s_i\)，且所有 \(k+1\) 个连通块中最大的大小为 \(M\)，则
第 \(i\) 个连通块的罚分即为 \(M−s_i\)。
Yazid 要求你在删除初始的树上的 k 条边后，获得所有连通块的罚分总和最小。
你还是觉得太简单了，但为了堵住 Yazid 的嘴，你决定亲自解决这个问题。

题解

赛时得分： 92/100 （这场因为没开 long long 挂了 23 pts）

首先我们可以把问题转化成求 \((k+1)M-n\) 的最小值。

我们发现只有 \(M\) 一个变量，所以我们尝试算他的最小值。

他是什么：最大连通块的最小值。显然可以二分。

如何 check，考虑在一个子树里面，我们什么时候要切边。显然是如果这个子树带上这个父亲要超过 \(M\) 的时候，同时，显然是切掉越大的不超过 \(M\) 的越好。

那么直接贪心，用一个大根堆去存一下子节点，如果这个地方要切就切。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n, m, sz[N], tmp, p;
vector<int>G[N];

void dfs(int u, int fa) {
    sz[u] = 1;
    priority_queue<pair<int, int> >Q;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        Q.push(make_pair(sz[v], v));
    }
    while(sz[u] > p) {
        ++tmp;
        sz[u] -= Q.top().first;
        Q.pop();
    }

}
bool check(int x) {
    tmp = 0;
    p = x;
    dfs(1, -1);
    return tmp <= m;
}

int main() {
    freopen("penalty.in", "r", stdin);
    freopen("penalty.out", "w", stdout);
    read(n, m);
    for(int i = 1; i < n; ++i) {
        int u, v;
        read(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int l = 1, r = n;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << (long long)l * (m + 1) - n << endl;
    return 0;
}