題目鏈接：點擊查看

題目大意：給出一棵樹表示一個國家，點1表示首都，現在需要分配 k 個城市為工業城市，其余 n - k 個城市為旅游城市，這個國家會定時在首都召開會議，換句話說，所有工業城市都必須派出一個使者到達首都（路徑唯一），使者經過的旅游城市的個數為幸福指數，問如何分配 k 個工業城市，能使得每次召開會議時，所有使者的幸福指數之和最大，輸出這個最大值

題目分析：首先不難看出，如果一個節點 x 想要變成工業城市時，當且僅當 x 的子樹中都已經是工業城市時最優，否則選擇子樹中的結點變為工業城市肯定更優，所以一開始可以從點1開始dfs，跑出每個節點的子樹大小 num[ i ]，以及深度 deep[ i ] （deep[ 1 ] = 0 ），這樣選擇一個節點 x 變成工業城市時的貢獻就是 deep[ i ] - ( num[ i ]? - 1 ) ，畫個圖不難看出來，排個序選前 k 個就行了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<int>node[N];int deep[N];LL num[N],temp[N];void dfs(int u,int fa,int dep) {deep[u]=dep;num[u]=1;for(auto v:node[u]){if(v==fa)continue;dfs(v,u,dep+1);num[u]+=num[v];}temp[u]=deep[u]-num[u]+1; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,k;scanf("%d%d",&n,&k);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs(1,-1,0);sort(temp+1,temp+1+n,greater<LL>());LL ans=0;for(int i=1;i<=k;i++)ans+=temp[i];printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1337C Linova and Kingdom(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。