CF802K Solution
2021/5/1 10:55:38
本文主要是介绍CF802K Solution,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题解
树形dp呐。
对于节点\(x\),每去向它的一个子结点,经过\(x\)的次数便会\(+1\)。因此如果最后回到\(x\)的话,最多可以去向\(k-1\)个子节点。但如果最后停留在\(x\)的子树当中,最多便可去向\(k\)个子节点。
状态:\(dp[i][j]\)表示以节点\(i\)为根的子树,是/否(\(j=1/0\))在其中结束时的边权最大和。
转移:设\(i\)的子结点个数为\(x\),\(j\)为\(i\)的子节点。\(dp[i][0]=dp[j][0]\)中最大的\(k-1\)个。\(dp[i][1]\)有2种情况:①在\(dp[i][0]\)前\(k\)大的子节点子树中结束,\(dp[i][1]=dp[i][0]+\)前\(k\)个节点中\(max(dp[j][1]-dp[j][0])+\)第\(k\)大的\(dp[j][0]\);②在其他子节点子树结束,\(dp[i][1]=dp[i][0]+\)其他节点中\(max(dp[j][1])\)。优先队列维护子节点\(dp\)值即可。
目标状态:\(dp[0][1]\)(易得\(dp[0][1]\ge dp[0][0]\))
AC代码
#include<bits/stdc++.h> #define mp make_pair using namespace std; const int N=1e5+10; int fst[N],nxt[2*N],v[2*N],w[2*N],cnt; int dp[N][2],ans,k; void add(int x,int y,int z) { v[++cnt]=y,w[cnt]=z; nxt[cnt]=fst[x],fst[x]=cnt; } void dfs(int x,int fa) { int tmp=0,qwq,qaq; priority_queue<pair<int,int> > q; for(int i=fst[x];i;i=nxt[i]) { int y=v[i]; if(y==fa) continue; dfs(y,x); q.push(mp(dp[y][0]+w[i],y)); } for(int i=1;i<k && !q.empty();i++) { dp[x][0]+=q.top().first; qwq=q.top().second; tmp=max(tmp,dp[qwq][1]-dp[qwq][0]); q.pop(); } if(q.empty()) {dp[x][1]=dp[x][0]+tmp; return;} qwq=q.top().second; tmp=max(tmp,dp[qwq][1]-dp[qwq][0])+q.top().first; while(!q.empty()) { qwq=q.top().second,qaq=q.top().first; q.pop(); tmp=max(tmp,qaq+dp[qwq][1]-dp[qwq][0]); } dp[x][1]=dp[x][0]+tmp; } int main() { int n,x,y,z; scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } dfs(0,-1); printf("%d",dp[0][1]); return 0; }
这篇关于CF802K Solution的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享