简要题意
给你一个 (n) 个节点 (m) 条边的树，定义”毛毛虫”为树中一条链和链上所有顶点所相连的边所组成的子树。求该树中点数最大的毛毛虫，输出点数。
比如，下面左边的树 (1) 中点数最大的毛毛虫就是右边的毛毛虫 (2)。
![P3174 [HAOI2009] 毛毛虫](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230605/2926148-20220928105146474-75032611.png)
![P3174 [HAOI2009] 毛毛虫](https://www.johngo689.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
(1 \leq m \lt n \leq 300000)
思路
一道没有看题解切掉的题。
下面我们称毛毛虫中的最长链为毛毛虫的”躯干”，将躯干上的点连向的非躯干的点的边称为”触手”。
如果我们将躯干上一个点的贡献看成点权的话，那么这就是一个求树上最长链的问题。
问题来了，如何求触手个数？答案就是，触手个数其实就是节点的度减去 (2)。
每个点的贡献需要加上自己，也就是说，每个点的贡献就是节点的度 减去 (1)。
但是首尾就会多减去 (1)，没事，最后加上 (2) 即可。但这又造成了问题，如果 (n = 1) 答案就是 (0+2=2)，事实上是 (1)（因为首尾相同，多加了），这里直接特判 (n=1) 即可。
求树上最长链使用两遍 DFS 大法。
代码
#include
using namespace std;
const int N = 600005;
struct edge{
int nxt,to;
} g[N];
int head[N],ec;
void add(int u,int v){
g[++ec].nxt=head[u];
g[ec].to=v;
head[u]=ec;
}
int n,m,w[N];
int ret,pos;
void dfs(int u,int fa,int sum){
if(sum>ret){
ret=sum;
pos=u;
}
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(v==fa){
continue;
}
dfs(v,u,sum+w[v]);
}
}
signed main(){
cin>>n>>m;
if(n==1){
cout<>x>>y;
add(x,y);add(y,x);
w[x]++;
w[y]++;
}
dfs(1,0,w[1]);
ret=0;
dfs(pos,0,w[pos]);
ret+=2;
cout<
Original: https://www.cnblogs.com/zheyuanxie/p/p3174.html
Author: xiezheyuan
Title: P3174 [HAOI2009] 毛毛虫
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604585/
转载文章受原作者版权保护。转载请注明原作者出处！