影石Insta360杯-2025牛客暑期多校训练营9——AVL tree

思路讲解

这道题目的想法实际上非常暴力。

DP状态定义

• dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。
  • 注意：高度正好h，根u保留。
  • 如果无法做到，设为INF（大数）。

问题描述

这道题给你一棵以节点1为根的二叉树（节点数n ≤ 2×10^5），但它可能不是AVL树（即高度平衡二叉树：每个节点左右子树高度差不超过1）。你可以通过三种操作来改造它：

1. 删除一个叶子节点。

2. 选择一个没有左孩子的节点，添加一个新节点作为它的左孩子。

3. 选择一个没有右孩子的节点，添加一个新节点作为它的右孩子。

目标是求最小操作次数，使整棵树变成AVL树。注意：操作可以任意次，包括删除原有节点或添加新节点，但根节点1必须保留（因为AVL树定义包括根）。

多测试用例，T ≤ 10000，但总∑n ≤ 2×10^5。

解题思路

我们用树形动态规划（DP）来解决这个问题。核心是计算每个子树的最小代价，使其成为指定高度的AVL树。

关键概念

• AVL树的定义：如题所述，空树高度0；否则高度 = max(左高, 右高) + 1，且|左高 - 右高| ≤ 1，且左右子树也是AVL。

• 操作的本质：

  • 删除叶子：相当于 pruning（修剪）不需要的部分。
  • 添加孩子：相当于在空位上建新子树。
  • 要平衡树，我们可能需要删除整个子树（代价 = 子树大小，因为要逐个删除叶子），然后从头建一个平衡的子树（代价 = 新添加的节点数）。

• 最****小节点数的AVL树：对于高度h的AVL树，最小节点数m[h]满足：

  • m[0] = 0（空树）
  • m[1] = 1（单节点）
  • m[h] = 1 + m[h-1] + m[h-2]（类似斐波那契，最小化节点：一侧高度h-1，另一侧h-2）
  • 这可以预计算，h最高取60就够，因为m[60]已经很大，超过n的范围。

DP状态定义

• dp[u][h]：以节点u为根的子树，改造为正好高度h的AVL树的最小操作次数（代价）。

  • 注意：高度正好h，根u保留。
  • 如果无法做到，设为INF（大数）。

• 最终答案：min over h (dp[1][h])，因为根树高度可以任意，只要平衡。

最关键的这个部分已经给出

vector<vll> dp(N+5,vll(H+5,INF));
dp[0][0]=0;
dp[0][1]=1;
FOR(h,2,H){
    dp[0][h]=dp[0][h-1]+dp[0][h-2]+1;
}
function<void (ll,ll)> dfs=[&](ll u,ll p){
    bool isleaf=true;
    vll wp;
    for(auto v:g[u]){
        if(v==p) continue;
        dfs(v,u);
        wp.EB(v);
        isleaf=false;
    }
    if(isleaf){
        dp[u][1]=0;
        dp[u][0]=1;
        FOR(h,2,H){
            dp[u][h]=dp[0][h]-1;
        }
        return;
    }
    if(SZ(wp)==1){
       wp.EB(0);
    }
    ll v=wp[0],v2=wp[1];
    vll ldp(H+5,INF),lldp(H+5,INF);
    FOR(h,1,H){
        ldp[h]=dp[v][h-1];
    }
    FOR(h,1,H){
        ldp[h]+=min({dp[v2][h-1],dp[v2][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        lldp[h]=dp[v2][h-1];
    }
    FOR(h,1,H){
        lldp[h]+=min({dp[v][h-1],dp[v][h-2<0?0:h-2]});
    }
    FOR(h,1,H){
        dp[u][h]=min(ldp[h],lldp[h]);
    }
    dp[u][0]=dp[u][1]+1;
    
};
dfs(1,1);

AC代码

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define EB emplace_back
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define lson(var) (var<<1)
#define rson(var) (var<<1|1)
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())
using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) { cerr << x; }
template<typename T> void _print(vector<T> v) { cerr << "[ "; for (T i : v) _print(i), cerr << " "; cerr << "]"; }
template<typename T> void _print(set<T> s) { cerr << "{ "; for (T i : s) _print(i), cerr << " "; cerr << "}"; }
template<typename T, typename U> void _print(pair<T, U> p) { cerr << "{"; _print(p.first); cerr << ", "; _print(p.second); cerr << "}"; }
template<typename T, typename U> void _print(map<T, U> m) { cerr << "{ "; for (auto &p : m) _print(p), cerr << " "; cerr << "}"; }
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>lT;
    while(lT--)
        __();
    return 0;
}
/*
    1
   2  3
 4   6 7
fabo[30]:832040
#ifdef LOCAL
vll fabo(30+3);fabo={0,1,1};
FOR(i,3,30){
    fabo[i]=fabo[i-1]+fabo[i-2];
}
debug(fabo[30]);
#endif
*/
inline void __(){
    cin>>N;
    vector<vector<ll>> g(N+5);
    ll H=30;
    FOR(i,1,N){
        ll u,v;
        cin>>u>>v;
        if(u!=0) g[i].EB(u),g[u].EB(i);
        if(v!=0) g[i].EB(v),g[v].EB(i);
    }
    vector<vll> dp(N+5,vll(H+5,INF));
    dp[0][0]=0;
    dp[0][1]=1;
    FOR(h,2,H){
        dp[0][h]=dp[0][h-1]+dp[0][h-2]+1;
    }
    function<void (ll,ll)> dfs=[&](ll u,ll p){
        bool isleaf=true;
        vll wp;
        for(auto v:g[u]){
            if(v==p) continue;
            dfs(v,u);
            wp.EB(v);
            isleaf=false;
        }
        if(isleaf){
            dp[u][1]=0;
            dp[u][0]=1;
            FOR(h,2,H){
                dp[u][h]=dp[0][h]-1;
            }
            return;
        }
        if(SZ(wp)==1){
           wp.EB(0);
        }
        ll v=wp[0],v2=wp[1];
        vll ldp(H+5,INF),lldp(H+5,INF);
        FOR(h,1,H){
            ldp[h]=dp[v][h-1];
        }
        FOR(h,1,H){
            ldp[h]+=min({dp[v2][h-1],dp[v2][h-2<0?0:h-2]});
        }
        FOR(h,1,H){
            lldp[h]=dp[v2][h-1];
        }
        FOR(h,1,H){
            lldp[h]+=min({dp[v][h-1],dp[v][h-2<0?0:h-2]});
        }
        FOR(h,1,H){
            dp[u][h]=min(ldp[h],lldp[h]);
        }
        dp[u][0]=dp[u][1]+1;
        
    };
    dfs(1,1);
    ll ans=minn(dp[1]);
#ifdef LOCAL
    FOR(i,1,N){
        _print(dp[i]);
    }
#endif
    cout<<ans<<"\n";
}
/*

*/

心路历程（WA，TLE，MLE……）