題目鏈接：點擊查看

題目大意：給出一棵樹，每個頂點都有權值，在樹上選出k個相互獨立的連通塊，使得其權值和的平均值最大的情況下選的塊數最多

題目分析：這個題目中平均值的優先級大于塊數，那么我們可以在樹上找到一塊權值最大的連通塊，記錄下他的權值后，在對于整棵樹搜索一下有幾個權值等于上述最大值并且相互獨立的連通塊，可以用樹形dp自底向上來記錄每棵子樹的最大權值和，對于每個頂點，我們可以選擇用或不用，計算出最大的權值和后再跑一邊dfs，求出有多少個符合條件的連通塊即可，不過不知道為什么我自己編了一組數據過不了，但是卻AC了。。數據也留一下吧

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e5+100;vector<int>node[N];int val[N];LL dp[N];LL mmax,ans;void dfs1(int u,int fa) {dp[u]=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs1(v,u);dp[u]+=max(dp[v],0LL);}mmax=max(mmax,dp[u]); }void dfs2(int u,int fa) {dp[u]=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa)continue;dfs2(v,u);dp[u]+=max(dp[v],0LL);}if(dp[u]==mmax){ans++;dp[u]=-inf;} }int main() { // freopen("input.txt","r",stdin)int n;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++){scanf("%d",val+i);node[i].clear();}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);}mmax=-inf;ans=0;dfs1(1,-1);dfs2(1,-1);cout<<mmax*ans<<' '<<ans<<endl;}/*61 3 -1 -1 1 11 32 33 44 54 6代碼答案：4 1我的答案：3 1*/return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1088E Ehab and a component choosing problem(树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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