cf 975 div2 C（结论）E (树+思维)

C
n 的范围小于 1e5 ,考虑枚举每组物品数量的上限，并算出根据已有的物品按照该限制至少分多少组M，之后可以求出补齐M组所需要的最少额外数量。
经典结论：
将N 种颜色的物品按每组上限c 个分组，保证每组物品颜色不同。最少的分组数为

所以可以算出所需要最少的额外数量，和K 比较就可。

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int sum = 0;
    int mx = -1;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }
    for (int i=n;i>=1;i--)
    {
        int len=max(mx,(sum+i-1)/i);
        int t=len*i-sum;
        if (t>=0&&t<=k)
        {
            cout<<i<<"\n";
            return;
        }
    }
}

E 题意：
给你一颗n个节点树，操作：可以将一个叶子节点和它相邻的边删去（这个操作可能会产生新的叶子节点）
问最少操作多少次 使得 所有的叶子 的深度相同。（根节点的深度是1）

假设操作完后，叶子节点的深度是 K
那么对于 深度大于K的节点都要删掉。（sub_sum）
对于 深度小于K 的节点，是否要删除，要看这个节点能到的最大深度，
dp_mx,我们要删除 dp_mx 小于K的节点。
点的个数 通过 数值桶的前缀和后缀来维护。

#include <bits/stdc++.h>
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const int N=5e5+10;
vector<int>e[N];
void solve()
{
    int n;cin>>n;
    for (int i=1;i<=n;i++)
        e[i].clear();
    vector<int>pre_sum(n+2);// 数值桶
    vector<int>sub_sum(n+2);
    vector<int>dp(n+1);// 每个节点的深度
    vector<int>dp_mx(n+1);// 每个 节点 能到达的最大深度
    for (int i=0,u,v;i<n-1;i++)
    {
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
   
    auto dfs=[&](auto && self,int u,int fa)->void
    {
        dp_mx[u]=dp[u];
        for (auto v:e[u])
        {
            if (v==fa)continue;
            dp[v]=dp[u]+1;
            self(self,v,u);
            dp_mx[u]=max(dp_mx[u],dp_mx[v]);
        }
        pre_sum[dp_mx[u]]++;
        sub_sum[dp[u]]++;
    };

     dp[1]=1;
    dfs(dfs,1,-1);
    for (int i=1;i<=n;i++)
    {
        pre_sum[i]+=pre_sum[i-1];
    }
    for (int i=n-1;i>=1;i--)
    sub_sum[i]+=sub_sum[i+1];
    int ans=n;
    for (int i=1;i<=n;i++)
    {
        ans=min(ans,pre_sum[i-1]+sub_sum[i+1]);
    }
    cout<<ans<<"\n";


}
int  main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    t = 1;
     cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}