CF1914F Programming Competition 贪心原则的DP?

终于理解了...

希望写给小伙伴们，希望大伙可以理解。

先确定贪心规则，即当最大子树不超过根子树减一的一半时，内部节点可以完全匹配。否则，可以先拿其他子树节点与最大子树内部节点匹配，子树内部再进行匹配。啥你说子树内部不够匹配怎么办？可以这么想，你这样都到匹配上限了，已经完全可以达到最优秀情况，取max即可。

设f[u]为以u为根的子树的最大匹配数。转移方程略。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=2e5+5;

int siz[N],n;
vector<int> son[N];
int f[N];

void find_siz(int u){
    siz[u]=1;
    for(int& v:son[u]){
        find_siz(v);
        siz[u]+=siz[v];
    }
}

void dfs(int u){
    int mx=-1;
    for(int v:son[u]){
        if(mx==-1||siz[v]>siz[mx]) mx=v;
        dfs(v);
    }
    if(mx==-1) {
        f[u]=0;
        return;
    }
    int res=siz[u]-siz[mx]-1;
    if(res>=siz[mx]){
        f[u]=(siz[u]-1)/2;
        return;
    }
    f[u]=min(res+f[mx],(siz[u]-1)/2);
}

void solve(){
    fill(f,f+N,0);
    fill(siz,siz+N,0);
    cin>>n;
    rep(i,0,n) son[i].clear();

    rep(i,2,n){
        int x;cin>>x;
        son[x].push_back(i);
    }
    find_siz(1);
    dfs(1);
    cout<<f[1]<<'\n';
}

signed main(){
    int T;
    cin>>T;
    while(T--)
        solve();
}