影石Insta360杯-2025牛客暑期多校训练营9——AVL tree · znzryb
## 思路讲解
这道题目的想法实际上非常暴力。
### DP状态定义
- dp[u][h]：以节点u为根的子树，改造为**正好高度h**的AVL树的最小操作次数（代价）。
- 注意：高度正好h，根u保留。
- 如果无法做到，设为INF（大数）。
### 问题描述
这道题给你一棵以节点1为根的二叉树（节点数n ≤ 2×10^5），但它可能不是AVL树（即高度平衡二叉树：每个节点左右子树高度差不超过1）。你可以通过三种操作来改造它：
1. 删除一个叶子节点。
1. 选择一个没有左孩子的节点，添加一个新节点作为它的左孩子。
1. 选择一个没有右孩子的节点，添加一个新节点作为它的右孩子。
目标是求最小操作次数，使整棵树变成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])，因为根树高度可以任意，只要平衡。
最关键的这个部分已经给出
```cpp
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代码
::: 源代码
```cpp
// 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……）