CF2031E sol

upd：修正了文中的一处错误。

动规妙妙题，代码完成于赛后一分钟内，诶诶。

题面大意

给你一颗有根树，现要生成一颗满二叉树，使得对该二叉树经过若干次删点操作后可以使两棵树同构。

删点操作定义为：选择一个非根节点 u，删去点 u，并把 u 的所有儿子与 u 的父亲连边。

求所需满二叉树高度的最小值，高度定义为根节点到叶子节点路径上的边数。

思路

设 dp_u 表示：可以通过删点操作与以 u 为根的子树同构的满二叉树高度最小值。

考虑转移，对于任意节点 u，现已知其所有儿子 v\in son_u 对应的 dp_v，则 dp_u 可以贪心求得。

每次选取所有儿子中二叉树高度最小的两个，设为 v_1 和 v_2，将这两颗二叉树合并，合并后的二叉树大小为 \max(dp_{v_1},dp_{v_2})+1，不断进行合并操作直到只剩一棵树即可，过程可使用优先队列实现。

注意转移时要特判 u 只有一个儿子的情况。因为出题人开大了时限，所以我们可以用深搜来转移它。

ACcode

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int T,n,dp[1000005];
vector<int>G[1000005];
void dfs(int u){
    if(G[u].size()==0)return;//叶子节点 
    for(int i=0;i<G[u].size();i++)dfs(G[u][i]);
    if(G[u].size()==1){//特判只有一个儿子
        dp[u]=dp[G[u][0]]+1;
        return;
    }
    priority_queue<int>q;
    for(int i=0;i<G[u].size();i++)q.push(-dp[G[u][i]]);//因为priority_queue默认大根堆，所以我们存负值以达到小根堆的效果
    while(q.size()>1){
        int x=q.top();q.pop();
        int y=q.top();q.pop();
        q.push(min(x,y)-1);//合并 
    }
    dp[u]=-q.top();//记得符号要变回来
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)G[i].clear(),dp[i]=0;//多测要清空 
        int u;
        for(int i=2;i<=n;i++){
            cin>>u;
            G[u].push_back(i);
        }
        dfs(1);
        cout<<dp[1]<<endl;//输出根节点对应的值 
    }
    return 0;
}