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