UOJ387 【UNR #3】To Do Tree 题解

题目链接：#387. 【UNR #3】To Do Tree

题意：

有一棵 \(n\) 个节点的有根树，\(1\) 号点为根节点。第 \(i\) 的父节点为 \(f_i\) (\(1\leq f_i < i \leq n\))。你每星期可以选择不超过 \(m\) 个节点删掉，需要保证被删掉的节点是没有父节点的。删完后，会剩下一个森林 (若干棵树)。求最少多少星期才能删完所有的节点。

输入格式：

第一行包含两个正整数 \(n,m\) (\(1\leq m\leq n\le 10^5\))。

第二行包含 \(n-1\) 个正整数 \(f_2,f_3,\cdots,f_n\) (\(1\leq f_i<i\leq n\))。

输出格式：

第一行输出一个整数 \(t\)，表示最少需要的时间。

接下来 \(t\) 行，第 \(i\) 行表示第 \(i\) 星期删的点，其中第一个整数 \(s_i\) 表示这周删的点的个数，接下来 \(s_i\) 个整数分别是这周肝的点的标号。

考虑贪心，每次选出子树大小最大的 \(m\) 个删掉。

正确性严谨证明参考OI中转站 ，反正我是凭感觉的，因为子树大小越大，删掉根后树的数量的期望更高。

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

代码：

#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 N ((int)(1e5 + 15))

int n,k,fa[N],sz[N],buf[N],len[N];
vector<int> vec[N]; priority_queue<pii> q;
void addEdge(int u,int v) { vec[u].push_back(v); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; int *f = buf, tot = 0;
    for(int i = 2; i <= n; i++) { cin >> fa[i], addEdge(fa[i], i); }
    for(int i = n; i; i--) sz[fa[i]] += (++sz[i]);
    for(q.emplace(sz[1], 1); !q.empty(); f += len[tot++])
    {
        int &cnt = len[tot];
        for(int i = k; !q.empty() && i; i--) { 
            f[cnt++] = q.top().second, q.pop();
        }
        for(int i = 0; i < cnt; i++)
            for(int v : vec[f[i]]) q.emplace(sz[v], v);
    }
    cout << tot << '\n'; f = buf;
    for(int i = 0; i < tot; f += len[i++])
    {
        cout << len[i] << ' ';
        for(int v = 0; v < len[i]; v++)
            cout << f[v] << " \n"[v + 1 == len[i]];
    }
    return 0;
}