视频链接:E64 树形DP P3174 [HAOI2009] 毛毛虫_哔哩哔哩_bilibili
P3174 [HAOI2009] 毛毛虫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 树形DP O(n) #include <iostream> #include <cstring> #include <algorithm> using namespace std;const int N=300005; int n,m,ans,du[N],f[N]; int head[N],idx; struct E{int v,ne;}e[N<<1];void add(int x,int y){e[++idx]={y,head[x]};head[x]=idx;du[x]++; //度 } void dfs(int u,int fa){f[u]=du[u];for(int i=head[u];i;i=e[i].ne){int v=e[i].v;if(v==fa)continue;dfs(v,u);ans=max(ans,f[u]+f[v]-1);f[u]=max(f[u],du[u]+f[v]-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);}dfs(1,0);cout<<ans+1<<endl; }