[HAOI2009]毛毛虫
2024-10-11 12:02:40
题目描述
对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 1 )抽出一部分就变成了右边的一个毛毛虫了(图 2 )。
输入输出格式
输入格式:
在文本文件 worm.in 中第一行两个整数 N , M ,分别表示树中结点个数和树的边数。
接下来 M 行,每行两个整数 a, b 表示点 a 和点 b 有边连接( a, b ≤ N )。你可以假定没有一对相同的 (a, b) 会出现一次以上。
输出格式:
在文本文件 worm.out 中写入一个整数 , 表示最大的毛毛虫的大小。
输入输出样例
输入样例#1:
13 12 1 2 1 5 1 6 3 2 4 2 5 7 5 8 7 9 7 10 7 11 8 12 8 13
输出样例#1:
11
说明
40% 的数据, N ≤ 50000
100% 的数据, N ≤ 300000
解题思路:树形DP
f[i]表示以i为根的子树的最长长度。
link[i]表示与i相连的点的个数
那么对于某个节点i,他对答案的贡献为:
由i扩展出去的最长链长度+由i扩展出去的次长链长度+与i相连的点的个数(注意更新时节点的重复)
#include<iostream> #include<cstdio> #include<algorithm> #define DB double #include<cmath> #define pi 3.1415926535898 using namespace std; inline int read() { int x=0,w=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') w=-1;ch=getchar();} while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*w; } const int N=300009; struct node{ int u,v,ne; }e[N*2]; int n,h[N],tot; void add(int u,int v) { tot++;e[tot]=(node){u,v,h[u]};h[u]=tot; } int m,link[N],f[N],ans; void dfs(int x,int fa) { int l1=-1,l2=-1; for(int i=h[x];i;i=e[i].ne) { int rr=e[i].v; if(rr==fa) continue; dfs(rr,x); if(f[rr]>l2) { if(f[rr]>l1) l2=l1,l1=f[rr]; else l2=f[rr]; } f[x]=max(f[x],f[rr]+link[x]-1); } ans=max(ans,l1+l2+link[x]-1); } int main() { n=read();m=read(); for(int i=1;i<=m;++i) { int x,y;x=read();y=read(); add(x,y);add(y,x); link[x]++;link[y]++; } for(int i=1;i<=n;++i) f[i]=1; dfs(1,0); printf("%d",ans); return 0; }
勿忘初心!
最新文章
- javascript数据结构与算法-- 二叉树
- COUNT(1)和COUNT(*)区别
- iOS搜索附近的位置(类似微博朋友圈位置)
- Centos6版本升级
- linux 安装 apache2.2.31
- graph-tool 练习
- Excel每隔两行自动求和一次怎么操作?
- WEB应用中的SESSION知多少?
- SharePoint2010 部署步骤“激活功能”中出现错误:无法启动计算机“PCName”上的服务SPUserCodeV4
- eclipse如何查看类之间的引用关系
- 初探linux子系统集之i2c子系统(二)
- C# 发展史
- docker安装与测试 及 安装docker compose
- python通过操作windows系统注册表方式修改环境变量
- python3-知识扩展扫盲易忘-zip的用法
- 【转】Java计算文件的hash值
- WF的简单使用
- Windows(x64)编译FFMPEG-2.0.1
- HBase1.2.0增删改查Scala代码实现
- C++(二十八) — 构造函数的初始化列表
热门文章
- 微信小程序多列选择器之range-key
- 详解 Vue 2.4.0 带来的 4 个重大变化
- thinkphp3.2.2邮箱发送
- 用Dedecms5.7的arclist标签调用文章内容
- ADO.NET复习总结(5)--工具类SqlHelper 实现登录
- eclipse中如何同期化
- 在ASP.NET Core中通过EF Core实现一个简单的全局过滤查询
- es6重点笔记:数值,函数和数组
- 阿里java开发手册中命名规约解读之DO/BO/DTO/VO/AO
- Linux 下 编译Xerces-c++