P3174 [HAOI2009]毛毛虫(树形dp)

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);

}