P3174 [HAOI2009]毛毛虫(树形dp)
2024-10-20 09:20:52
P3174 [HAOI2009]毛毛虫
题目描述
对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 1 )抽出一部分就变成了右边的一个毛毛虫了(图 2 )。
输入输出格式
输入格式:
在文本文件 worm.in 中第一行两个整数 N , M ,分别表示树中结点个数和树的边数。
接下来 M 行,每行两个整数 a, b 表示点 a 和点 b 有边连接( a, b ≤ N )。你可以假定没有一对相同的 (a, b) 会出现一次以上。
输出格式:
在文本文件 worm.out 中写入一个整数 , 表示最大的毛毛虫的大小。
输入输出样例
说明
40% 的数据, N ≤ 50000
100% 的数据, N ≤ 300000
/*
类似dfs求直径
r[]为入度
一条毛毛虫的点数为
Σr[i]-(链长-1)+1
=Σ(r[i]-1)+2
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 300007 using namespace std;
int n,m,ans,cnt,S,T;
int head[N],deep[N],pre[N];
int r[N];
struct edge{
int u,v,net;
}e[N<<]; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void add(int u,int v)
{
e[++cnt].v=v;e[cnt].net=head[u];head[u]=cnt;
} void dfs(int u,int fa,int num)
{
if(num>ans) S=u,ans=num;
for(int i=head[u];i;i=e[i].net)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u,num+r[v]);
}
} int main()
{
int x,y;
n=read();m=read();
memset(r,-,sizeof r);
for(int i=;i<n;i++)
{
x=read();y=read();
add(x,y);add(y,x);
r[x]++;r[y]++;
}
dfs(,,r[]);ans=;
dfs(S,,r[S]);
printf("%d\n",ans+);
return ;
}
/*
把链连带链上的点的儿子算作一条链
f[x]表示以x为根最大链的大小
维护以某个点为根最大链和次大链计算答案
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define N 300007 using namespace std;
int f[N],head[N],son[N];
int n,m,k,ans,maxx;
struct edge
{
int to,net;
}e[N<<]; inline void add(int u,int v)
{
e[++k].to=v;e[k].net=head[u];head[u]=k;
} inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} void dfs(int u,int fa)
{
int v,bigx=,lowx=;
for(int i=head[u];i;i=e[i].net)
{
v=e[i].to;
if(v!=fa)
{
dfs(v,u);
if(f[v]>lowx)//维护最大链与次大链
{
if(f[v]>bigx)lowx=bigx,bigx=f[v];
else lowx=f[v];
}
f[u]=max(f[u],f[v]+son[u]-);
}
}
ans=max(ans,lowx+bigx+son[u]-);//(-1是因为根节点重复加了)
} int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
int u,v;
u=read();v=read();
add(u,v);add(v,u);
son[u]++;son[v]++;
}
for(int i=;i<=n;i++)f[i]=;
dfs(,);
printf("%d",ans);
}
最新文章
- Java GUI编程
- 如何安装win10+Red Hat Enterprise Linux双系统?
- POJ3207Ikki&#39;s Story IV - Panda&#39;s Trick(模板题)
- 如何让div水平垂直居中
- MySQL 中随机抽样:order by rand limit 的替代方案
- linux printk函数学习
- .NET开发人员必须知道的八个网站
- 它们的定义actionbar 并删除留空
- Sping--Id, Name
- 详解 try-with-resource
- vijos1698题解
- 通俗的讲法理解spring的事务实现原理
- Vector简单介绍
- Asp.Net WebApi 使用OWIN架构后,出现 “没有 OWIN 身份验证管理器与此请求相关联(No OWIN authentication manager is associated with the request)” 异常的解决办法
- jupyter依赖tornado版本
- 使用sshfs将远程目录挂载到本地
- oracle密码过期的修改
- db2 表空间扩容
- stl源码剖析 详细学习笔记 hashtable
- ZOJ 3765 Lights (伸展树splay)
热门文章
- 【07】Ajax status和statusText状态对照表
- HDU 1016 素数环问题
- cf 55D 数位dp 好题
- redis持久化机制【十三】
- Google Protocol Buffer 的使用(一)
- [bzoj1014][JSOI2008]火星人prefix_非旋转Treap_hash_二分
- python 进程内存增长问题, 解决方法和工具
- python爬虫实践--求职Top10城市
- javascript下的json 序列化及反序列化
- JS 通过选择百度地图地址获取经纬度自动填充到文本框中的方法