NOIP2019提高組模拟–拆網線

【題解】

貪心加DP

重點在于找到圖中所有可以形成兩點一線的圖形（且盡可能地多）然後再多的減少的加；

在其他部落格上也有用拓撲序的大牛

我們定 DP[i][0∼1] 表示該節點是否與他的父親節點連接配接時的最大獨立邊集，那麼我們可以得到轉移方程

DP[i][0]=∑DP[j][0]+max(max(DP[j][1]−DP[j][0]),0)

DP[i][1]=∑DP[j][0]

那麼這棵樹的最大獨立邊集就為 DP[1][0]， 如果 K 大于最大邊集 * 2，那麼我們還需多連 K−DP[1][0]∗2 的邊，如果小于那我們需要連 K/2+(Kand1)邊。

#include<bits/stdc++.h>
using namespace std;
int dp[100005][2];
struct tree{
    int fa;
    vector<int>son;
}t[100005];
void dfs(int cur){
    dp[cur][1]=dp[cur][0]=0;
    for(int i=0;i<t[cur].son.size();++i){
        int v=t[cur].son[i];
        dfs(v);
        dp[cur][0]+=max(dp[v][1],dp[v][0]);
    }
    for(int i=0;i<t[cur].son.size();++i){
        int v=t[cur].son[i],x;
        if((x=dp[cur][0]-max(dp[v][0],dp[v][1])+dp[v][0]+1)>dp[cur][1]){
            dp[cur][1]=x;
        }
    }
}
int main(){
    int T;
    cin>>T;
    while(T--){
        memset(dp,0,sizeof(dp));
        memset(t,0,sizeof(t));
        int n,k;
        cin>>n>>k;
        for(int i=2;i<=n;++i){
            int fa;
            cin>>fa;
            t[fa].son.push_back(i);
            t[i].fa=fa;
        }
        dfs(1);
        int ans=max(dp[1][0],dp[1][1]);
        if(k<=ans*2){
            cout<<(k+1)/2<<endl;
        }
        else{
            cout<<ans+k-ans*2<<endl;
        }
    }
    return 0;
}