P3174 [HAOI2009]毛毛虫

题目描述

对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 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

/*
类似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);
}

最新文章

  1. Java GUI编程
  2. 如何安装win10+Red Hat Enterprise Linux双系统?
  3. POJ3207Ikki&#39;s Story IV - Panda&#39;s Trick(模板题)
  4. 如何让div水平垂直居中
  5. MySQL 中随机抽样:order by rand limit 的替代方案
  6. linux printk函数学习
  7. .NET开发人员必须知道的八个网站
  8. 它们的定义actionbar 并删除留空
  9. Sping--Id, Name
  10. 详解 try-with-resource
  11. vijos1698题解
  12. 通俗的讲法理解spring的事务实现原理
  13. Vector简单介绍
  14. Asp.Net WebApi 使用OWIN架构后,出现 “没有 OWIN 身份验证管理器与此请求相关联(No OWIN authentication manager is associated with the request)” 异常的解决办法
  15. jupyter依赖tornado版本
  16. 使用sshfs将远程目录挂载到本地
  17. oracle密码过期的修改
  18. db2 表空间扩容
  19. stl源码剖析 详细学习笔记 hashtable
  20. ZOJ 3765 Lights (伸展树splay)

热门文章

  1. 【07】Ajax status和statusText状态对照表
  2. HDU 1016 素数环问题
  3. cf 55D 数位dp 好题
  4. redis持久化机制【十三】
  5. Google Protocol Buffer 的使用(一)
  6. [bzoj1014][JSOI2008]火星人prefix_非旋转Treap_hash_二分
  7. python 进程内存增长问题, 解决方法和工具
  8. python爬虫实践--求职Top10城市
  9. javascript下的json 序列化及反序列化
  10. JS 通过选择百度地图地址获取经纬度自动填充到文本框中的方法