题解：CF2031E Penchick and Chloe's Trees

Problem

将一棵满二叉树删为一棵指定的树，每次删除节点会将其所有儿子连到父亲节点上，求初始二叉树的最小高度。

Solution

O(n^2)

记 f_i 表示节点 i 子树内操作完成的最小高度，考虑转移。\ 显然我们应该将高度低的子节点和高度低的子节点优先合并。设当前节点为 x，每个高度与 x 相差 k 的节点可以放 2^k 个，可以看作“占据”了节点 x 的 \frac{1}{2^k} 的空间。因为每个子节点的大小都是 2 的整数次幂，所以不必担心某个节点因空间不连续而放不下。\ 充分发扬人类智慧，发现这个过程与高精加非常相似。\ 具体地，将每个子节点 y 看作一个二进制数 2^{f_y}，每个节点跑一遍高精加，有以下转移（注意 f_x 应大于 \max f_y）：

用 bitset 可以做到 O(\frac{n^2}{\omega})，虽然没什么用。

O(n\log n)

考虑优化高精加的过程。\ 因为我们只关心 \lceil\log_2\sum 2^{f_y}\rceil 的值，所以较低位可以舍去。\ 将所有儿子的 f 值存起来排序，从低到高位考虑，同时记录进位。\ 高精加的每个数都是 2 的整数次幂，所以进位数量仅有 O(n) 个，可以存下。\ 从一位 p 进到另一位 p+d 时，将进位数量 w 更新为 \lceil\frac{w}{2^d}\rceil。\ 最后将剩余的进位加上 \max f_y，即为 \lceil\log_2\sum 2^{f_y}\rceil 的值。

Code

（场上没发现进位 w 的贡献是 \lceil\log_2w\rceil，代码里面 O(\log n) 求了。预处理即可。

#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define R read()
using namespace std;
inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x;
}
const int inf=0x3f3f3f3f,N=1000005;
const ll INF=0x3f3f3f3f3f3f3f3f;
int T,n,f[N],p2[25];
vector<int> v[N];
void dfs(int x){
    if(!v[x].size()){ f[x]=0; return; }
    int mx=0;
    vector<int> s;
    for(int y:v[x]){
        dfs(y);
        s.pb(f[y]);
        mx=max(mx,f[y]);
    }
    sort(s.begin(),s.end());
    int w=0,lst=0,cnt=0;
    for(int y:s){
        if(y-lst>22&&w) w=1;
        else w=ceil(1.0*w/p2[y-lst]);
        w++;
        lst=y;
    }
    while(w>1) w=ceil(w/2.0),cnt++;
    f[x]=max(mx+1,s.back()+cnt);
}
int main(){
    T=R;
    p2[0]=1;
    for(int i=1;i<25;i++) p2[i]=p2[i-1]<<1;
    while(T--){
        n=R;
        for(int i=1;i<=n;i++) v[i].clear();
        for(int i=2;i<=n;i++) v[R].pb(i);
        dfs(1);
        printf("%d\n",f[1]);
    }
    return 0;
}