【2】做题心得 - 2025 NOIP #68 - T3【二分】【动态规划】【树形 DP】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+10;
int n,dp[N],f[N];
int lmt,res;
vector<int>e[N];
void dfs(int p,int fa){
    if(fa&&e[p].size()==1) 
        return f[p]=1, void(0);
    int S=0;
    for(auto v:e[p])if(v^fa)
        dfs(v,p), S+=f[v];
    dp[0]=1;
    for(int i=1;i<=lmt;i++) dp[i]=0;
    for(auto v:e[p])if(v^fa)
        for(int i=lmt;i>=f[v];i--)
            dp[i]|=dp[i-f[v]];
    f[p]=p!=1;
    for(int i=lmt;i>=0;i--)if(dp[i])
        { f[p]+=S-i; break; }
    if(f[p]>lmt) res=0;
    return;
}
bool check(int x){
    res=1, lmt=x, dfs(1,0);
    return res;
}
void solve(){
    for(int i=1;i<=n;i++)
        e[i].clear(), f[i]=0;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int l=0,r=n;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<"\n";
    return;
}
int main(){
    freopen("balance.in","r",stdin);
    freopen("balance.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}