1 solutions
-
2
其实整个问题是具有可DP性的,以1为根,设
dp[i][0/1]
表示:dp[i][0]
表示 以i
节点为根的子树,不需要父节点的安利的情况下,自己内部能全部用上CourseBench的代价。dp[i][1]
表示 以i
节点为根的子树,需要父节点的安利的情况下,自己内部能全部用上CourseBench的代价。
注意到
dp[i][0] >= dp[i][1]
然后dp就行了。
设当前点度数为
deg
,转移为:- 把自己染黑,
dp[i][0]
: 选择子树最小的个dp[u][0]
,剩下加上dp[u][1]
dp[i][1]
: 选择子树最小的个dp[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