1 solutions

  • 2
    @ 2022-9-11 22:59:36

    其实整个问题是具有可DP性的,以1为根,设dp[i][0/1]表示:

    • dp[i][0] 表示 以i节点为根的子树,不需要父节点的安利的情况下,自己内部能全部用上CourseBench的代价。
    • dp[i][1] 表示 以i节点为根的子树,需要父节点的安利的情况下,自己内部能全部用上CourseBench的代价。

    注意到dp[i][0] >= dp[i][1]

    然后dp就行了。

    设当前点度数为deg,k=deg2k=\lfloor {\deg\over 2} \rfloor转移为:

    • 把自己染黑,=min(dp[u][0],dp[u][1])+1=\sum \min (dp[u][0],dp[u][1])+1
    • dp[i][0]: 选择子树最小的kkdp[u][0],剩下加上dp[u][1]
    • dp[i][1]: 选择子树最小的k1k-1dp[u][1],剩下加上dp[u][1]
    #include<bits/stdc++.h>
    using namespace std;
    int qr(){
    	int ret=0,c=getchar();
    	while(!isdigit(c)) c=getchar();
    	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
    	return ret;
    }
    const int maxn=1e6+5;
    int n;
    vector<int>e[maxn];
    int dp[maxn][2];
    
    void add(int fr,int to){
    	e[fr].push_back(to);
    	e[to].push_back(fr);
    }
    
    void dfs(int now,int last){
    	for(auto t:e[now])
    		if(t^last)
    			dfs(t,now);
    	int k=(e[now].size()+1)/2,sum=0;
    	vector<int>ve,fe;
    	for(auto t:e[now])
    		if(t^last)
    			ve.push_back(min(dp[t][0],dp[t][1])),fe.push_back(dp[t][0]-ve.back()),sum+=ve.back();
    	sort(ve.begin(),ve.end());
    	sort(fe.begin(),fe.end());
    	//dp(i,0)
    	dp[now][0]=dp[now][1]=sum+1;
    	if((int)ve.size()>=k){
    		int sum2=0;
    		for(int t=0;t<k;++t)
    			sum2+=fe[t];
    		dp[now][0]=min(dp[now][0],sum2+sum);
    	}
    	if((int)ve.size()>=k-1){
    		int sum2=0;
    		for(int t=0;t<k-1;++t)
    			sum2+=fe[t];
    		dp[now][1]=min(dp[now][1],sum2+sum);
    	}
    	//cout<<dp[now][0]<<' '<<dp[now][1]<<endl;
    }
    
    int main(){
    	n=qr();
    	for(int t=1;t<n;++t)
    		add(qr(),qr());
    	dfs(1,0);
    	cout<<dp[1][0]<<endl;
    	return 0;
    }
    

    Information

    ID
    158
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    350
    Accepted
    7
    Uploaded By