题面

题目描述

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

题解

设f[i]表示以i为根节点的子树所能够构成的最大毛毛虫

直接推出来即可

注意的是：毛毛虫可以是根节点的两条链连接起来

所以还需要计算第二长的毛毛虫

最后输出结果即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 300100

inline int read()

{

      register int x=0,t=1;

      register char ch=getchar();

      while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

      if(ch=='-'){t=-1;ch=getchar();}

      while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}

      return x*t;

}

struct Line

{

      int v,next;

}e[MAX*2];

int h[MAX],cnt=1,ans;

int Son[MAX],f[MAX];

inline void Add(int u,int v)

{

      e[cnt]=(Line){v,h[u]};

      h[u]=cnt++;

}

void GetSon(int u,int ff)

{

      for(int i=h[u];i;i=e[i].next)

      {

               int v=e[i].v;

               if(v!=ff)

               {

                   ++Son[u];

                 GetSon(v,u);

               }

      }

}

void DFS(int u,int ff)//树形DP

{

      int max1=0,max2=0;

      for(int i=h[u];i;i=e[i].next)

      {

              int v=e[i].v;

              if(v!=ff)

              {

                   DFS(v,u);

                   if(f[v]>max2)

                   {

                           if(f[v]>max1)

                           {

                                  max2=max1;

                                  max1=f[v];

                           }

                           else

                                  max2=f[v];

                   }

                   f[u]=max(f[u],f[v]+Son[u]-1);

              }

      }

      ans=max(ans,max1+max2+Son[u]-1);

}

int main()

{

      int N=read();

      int M=read();

      for(int i=1;i<=M;++i)

      {

                int u=read(),v=read();

                Son[u]++;Son[v]++;

              Add(u,v);

                Add(v,u);

      }

      for(int i=1;i<=N;++i)

         f[i]=1;

      DFS(1,1); 

      //f[i]表示以i为根节点的最大毛毛虫。 

      cout<<ans<<endl;

      return 0;

}