M_sea

洛谷3174 [HAOI2009]毛毛虫
题目描述对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下...
扫描右侧二维码阅读全文
23
2018/08

洛谷3174 [HAOI2009]毛毛虫

题目描述

对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 1 )抽出一部分就变成了右边的一个毛毛虫了(图 2 )。

7967.png

传送门

算法

考虑树形DP。

设$f[u]$表示以$u$为根的子树走到底,不算父节点的最大毛毛虫的节点数。

再设$son[u]$表示与$u$直接相连的点数。

那么枚举子节点$v$,可以得到:

$$f[u]=max(f[v]+son[u]-1)$$

但是因为毛毛虫可以是根节点的两条链连接起来,所以要统计一下最大和次大的毛毛虫,再加起来。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
#define max_(a,b) ((a)>(b)?(a):(b))
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

struct Edge { int v,nxt; };
Edge e[600010];
int head[300010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int son[300010];
int f[300010];
int ans=0;

inline void Dfs(int u,int fa) {
    int ans1=0,ans2=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa) continue;
        Dfs(v,u);
        if (f[v]>ans1) ans2=ans1,ans1=f[v];
        else if (f[v]>ans2) ans2=f[v];
        f[u]=max_(f[u],f[v]+son[u]-1);
    }
    ans=max_(ans,ans1+ans2+son[u]-1);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read();
        addEdge(x,y);
        addEdge(y,x);
        son[x]++,son[y]++;
    }
    for (re int i=1;i<=n;++i) f[i]=1;
    Dfs(1,0);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 20 PM

发表评论