[HAOI2009]毛毛虫

本文主要是介绍[HAOI2009]毛毛虫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

LuoguP3174 [HAOI2009]毛毛虫

分析

可以想到这是一个树形DP：因为题目要求一条链，并且这条链连同其相邻节点所组成的新树最长，所以这就意味着，选择一个节点后，将选择其所有儿子，并且扩展其中一个儿子。
因此可以得到一个暴力做法：枚举每个点，树形DP，设f[i]表示以i为根节点的最长链长度。
转移方程：$f[i]=max\{f[v]+son[i]-1|v\to i \}$（要减去被选中的点，因为每个点应初始化为1，否则单点情况无法处理，这样就导致被选中的儿子在son[i]中算了一次，在f[v]中又算了一次，也就是被多算了一次）
复杂度取决于儿子大小，即使是一棵二叉树，也有$O(2^{\log_2 n}*n)=O(n^2)$，显然过不了。
观察树的性质，可以发现：钦定任意一节点为根，那么答案树就是：此节点、其最长链上满足条件的点、次长链上满足条件的点。这一点很难想，不过学会这种思维之后，其他的题目就说不定能想到了。
优化做法：钦定一个节点为根进行dfs，每个节点保存一个次大答案s，最大答案l：

$$f[u]=max\{f[v]+son[i]-1|v\to i \},ans=max\{ l[u]+s[u]+son[u]-1\};$$
注意更新时要判断f[u]与l、s的大小，逐个更新。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=300002;
struct Edge{int to,next;
}e[maxn*2];
int head[maxn],f[maxn],son[maxn];
bool vis[maxn];
int n,m,cnt,ans;void add(int u,int v)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;son[u]++;
}void dfs(int u,int fa)
{int s=0,l=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa)   continue;dfs(v,u);if(f[v]>s){if(f[v]>l)  s=l,l=f[v];else        s=f[v];f[u]=max(f[u],f[v]+son[u]-1);}}ans=max(ans,s+l+son[u]-1);
}int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);add(x,y),add(y,x);}for(int i=1;i<=n;i++)   f[i]=1;dfs(1,0);printf("%d",ans);return 0;
}

这篇关于[HAOI2009]毛毛虫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---