P3174 [HAOI2009]毛毛虫
2021/9/14 23:04:44
本文主要是介绍P3174 [HAOI2009]毛毛虫,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Jisoo
\(dp_i\)表示节点i为头的最长毛毛虫
(我这里i的父节点呗算作腿的一条)
然后就可以不用特判地进行转移
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define int long long using namespace std; int n,m; struct ed{ int to; int ne; }ed[600005]; int p; int head[300005]; int dp[300005]; int ans; void add(int f,int to){ p++; ed[p].to=to; ed[p].ne=head[f]; head[f]=p; } int x,y; int num[300005]; void dfs(int r,int f){ dp[r]=num[r]+1; int mx1=0; int mx2=0; for(int i=head[r];i;i=ed[i].ne){ if(ed[i].to==f) continue; int v=ed[i].to; dfs(v,r); dp[r]=max(dp[r],dp[v]+num[r]-1); if(dp[v]>mx1){ mx2=mx1; mx1=dp[v]; }else if(dp[v]>mx2) mx2=dp[v]; } ans=max(max(ans,dp[r]),mx1+mx2-3+num[r]); return ; } signed main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ scanf("%d%d",&x,&y); add(x,y); add(y,x); num[x]++; num[y]++; } dfs(1,0); cout<<ans; return 0; }
这篇关于P3174 [HAOI2009]毛毛虫的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-14折腾之王:JavaScript 之父 Brave 浏览器与 BAT 的诞生
- 2025-01-13从协作到创新:电商团队效率提升新方法
- 2025-01-13汉服销售拓展客源,能精准投放广告的软件求推荐!蛇年新春!
- 2025-01-13提升客户体验的关键:电商团队协作效率优化
- 2025-01-13不触碰资金的支付网关有哪些?
- 2025-01-13如何运用敏捷开发的6大模型来提高团队工作效率?
- 2025-01-13汉服制作质量检测,能高清放大细节的软件用哪个?2025 新春!
- 2025-01-13团队目标管理的6种实用方法(附OKR模板)
- 2025-01-13短剧制片的幕后:如何通过协同编辑提升效率
- 2025-01-13B端产品业务调研:系统步骤与策略解析