题解：P15037 「chaynOI R2 T2」熟练地剖分

· · 题解

每一轮至少会缩掉一个点，所以最终一定会成为一个点，轮数是 O(n) 的，暴力模拟时间复杂度为 O(n^2)。

考虑它为什么慢，比如有一个点，之后很多轮都没有被操作，然后你每一次都扫了它，所以就爆了。

那能否设计一种方法使得在能够预测一个节点被选择的时机时就不扫它了。

特殊性质有一个提示，对于一个菊花，它每一次都会固定减少一个叶子节点，答案为 n-1。

你发现对于这些叶子节点我们不关心它减少的顺序，也就是说可以只记录当前节点的儿子中，叶子节点的个数。如果没有非叶子节点作为重儿子就直接从里面扣一个即可。

考虑维护当前所有非叶子节点，动态维护每一个点的非叶子重儿子，以及它下面挂的叶子节点数量，对于一个节点：

然后这个时候可以直接更新它父亲的重儿子，免去更麻烦的步骤。

然后这个非叶子节点的集合需要支持快速删点，从大到小枚举元素，链表即可。合并重儿子的部分可以用并查集维护。

显然你扫到每一个节点一定会在三个中执行一个，那就至少会删掉一个节点，也就是消耗了一个全局的资源，每一种操作次数都是 O(n) 的，每个节点最多被删一次，时间复杂度 O(n)。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 5;
int prv[N], nxt[N], tail;
int n, ans, fa[N], sz[N], cnt[N], son[N];
struct DSU
{
    int fa[N];
    void init()
    {
        iota(fa + 1, fa + n + 1, 1);
        return;
    }
    int find(int x)
    {
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void merge(int x, int y)
    {
        x = find(x), y = find(y);
        if(x == y) return;
        fa[x] = y;
        return;
    }
}dsu;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n;
    for(int i = 2; i <= n; i++) cin >> fa[i];
    dsu.init();
    for(int i = 1; i <= n; prv[i] = i - 1, nxt[i] = i + 1, i++);
    nxt[0] = 1, prv[n + 1] = n, tail = n;
    auto del = [&](int x)
    {
        nxt[prv[x]] = nxt[x], prv[nxt[x]] = prv[x];
        if(x == tail) tail = prv[x];
    };
    while(tail > 1)
    {
        ++ans;
        for(int i = tail; i; sz[i] = son[i] = 0, i = prv[i]);
        for(int i = tail; i; i = prv[i])
        {
            if(!son[i] && !cnt[i])
            {
                del(i);
                ++cnt[fa[i]];
                continue;
            }
            sz[i] += cnt[i] + 1;
            if(!son[i]) --cnt[i];
            else
            {
                del(son[i]);
                dsu.merge(son[i], i);
                cnt[i] += cnt[son[i]];
            }
            if(i > 1)
            {
                sz[fa[i]] += sz[i];
                if(sz[i] >= sz[son[fa[i]]]) son[fa[i]] = i;
            }
        }
        for(int i = tail; i; i = prv[i]) fa[i] = dsu.find(fa[i]);
    }
    cout << ans + cnt[1];
    return 0;
}

:::