題目鏈接：點擊查看

題目大意：給出一棵包含n個節點的樹，每個節點都有一個權值，整棵樹的根是點1，問從點1開始向下一直走到葉子節點，可以走k次，怎么樣走權值和最大，每個節點被走過一次后權值會變為0

題目分析：這個題有兩個方法可以做，先說一下比較好想的一種吧：

樹形dp：

我們需要考慮應該怎樣dp，因為每次都是從1節點向下走到葉子節點，可以先求出來最長鏈，即從點1到某一葉子節點權值最大的一條鏈，我們可以自底向上的維護子樹中最大的一條鏈，不斷向上轉移，最終得出結果，那么我們已經得到了這條最長鏈后該怎么處理呢，接下來我們需要自頂向下的去將每條鏈上的節點權值都加到根節點上，最長鏈上的節點毋庸置疑都會加到點1上，那么其他沒有遍歷到的節點該怎么處理呢，我們也是需要自頂向下，將他們的各自所屬鏈上的節點權值分別加到他們分支下來的那個點上，這樣就避免會重復增加，最后對每條鏈排個序，求出前k大的加和就行，上代碼：

#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=1e5+100;LL val[N];vector<int>node[N];int son[N];//記錄最大鏈上的子節點LL sum[N],dp[N];//分別記錄子樹上最大鏈的權值和，dp[i]指的是以i為根節點的最大鏈權值和 //sum數組主要是輔助找到權值最大的鏈用的，即輔助更新son數組void dfs(int u,int fa)//找到權值最大的鏈 {sum[u]=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(fa==v)continue;dfs(v,u);if(son[u]==-1||sum[v]>sum[son[u]]){son[u]=v;}}if(son[u]!=-1)sum[u]+=sum[son[u]]; }void dfs2(int u,int fa,int root)//更新dp數組 {dp[root]+=val[u];if(son[u]!=-1){dfs2(son[u],u,root);}for(int i=0;i<node[u].size();i++){int v=node[u][i];if(v==fa||v==son[u])continue;dfs2(v,u,v);} }bool cmp(LL a,LL b) {return a>b; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0;while(w--){int n,k;memset(son,-1,sizeof(son));memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",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);}dfs(1,-1);dfs2(1,-1,1);sort(dp+1,dp+1+n,cmp);LL ans=0;for(int i=1;i<=k;i++)ans+=dp[i];printf("Case #%d: %lld\n",++kase,ans);}return 0; }

樹上貪心：

這個思路很簡單，但是卻不好想，所以加了一個思維的標簽，因為題目中給出的是有向圖，我們可以反向建圖，這樣從每一個葉子節點到根節點的路徑都變成唯一的了，可以用dfs先遍歷一邊每個葉子節點，求出每一條路徑上的權值，從大到小排個序，然后在從頭跑一邊，不過這次跑就需要標記點了，已經標記過的點，即已經走過的點就不能再走了，然后在更新一邊剛才儲存的權值和，最后排個序輸出前k個的和就好了，實現很簡單，但是思路不好想，上代碼：

#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=1e5+100;LL val[N],dp[N];int in[N];//記錄每個點的入度bool vis[N];struct Node {LL sum;int u;Node(){sum=u=0;}bool operator<(Node a)const{return sum>a.sum;} }a[N];vector<int>node[N];LL dfs(int u)//搜索從每個葉子節點走到根節點的權值和 {if(dp[u]!=-1)return dp[u];LL temp=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];temp+=dfs(v);}return dp[u]=temp; }LL dfs2(int u)//根據每個頂點只能走一次的特性，更新權值和 {LL temp=val[u];for(int i=0;i<node[u].size();i++){int v=node[u][i];if(vis[v])continue;vis[v]=true;temp+=dfs2(v);}return temp; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0;while(w--){int n,k;memset(in,0,sizeof(in));memset(vis,false,sizeof(vis));memset(dp,-1,sizeof(dp));scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",val+i);node[i].clear();}for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[v].push_back(u);//反向建圖in[u]++;}int cnt=0;for(int i=1;i<=n;i++)if(!in[i]){a[cnt].u=i;a[cnt++].sum=dfs(i);}sort(a,a+cnt);for(int i=0;i<cnt;i++)a[i].sum=dfs2(a[i].u);sort(a,a+cnt);LL ans=0;for(int i=0;i<min(k,cnt);i++)ans+=a[i].sum;printf("Case #%d: %lld\n",++kase,ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 5242 Game(树形dp+树链剖分/树上贪心+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

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