【HAOI】毛毛虫

题面描述

输入输出格式

输入输出

数据范围

先分析一波题面，我刚看到这个题，我整个人都傻了，我一直在纠结啥叫像毛毛虫，导致我根本不知道定义是什么，后来才知道毛毛虫就是一条链+链上所有点的子节点，因为题目要求毛毛虫要尽量的大，那解法就是找一条链，使链上所有的节点数最多即可之前我一直在把最大值加上去，但是导致一直是错的，看了题解才发现不止光要最大值，还是要次大值，而且还要提醒一下求节点数最大的一条链，而不是最长链，因为最长链并非是节点数最大的一条链，这就要涉及到dfs遍历，由最后一层返回过来，找出每个点向上回溯的最大值和次大值，到最后再更新一下sum即可。

毒瘤题，做的我想哭

#include<bits/stdc++.h>
using namespace std;
const int oi=2000010;
long long n,m,ver[oi],head[oi],ne[oi],d1[oi],edge[oi],d2[oi],s[oi],tot=0,si[oi],sum=0;
void add(long long x,long long y,long long z)
{
	ver[++tot]=y;
	edge[tot]=z;
	ne[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int y)
{
	int maxx1=0,maxx2=0;
	for(int i=head[x];i;i=ne[i])
	{
		if(ver[i]==y)
		continue;
		dfs(ver[i],x);
		if(d1[ver[i]]>maxx1)
		{
			maxx2=maxx1;
			maxx1=d1[ver[i]];
		}
		else if(d1[ver[i]]>maxx2)
		{
			maxx2=d1[ver[i]];
		}
		d1[x]=max(d1[x],d1[ver[i]]+s[x]-1);
	}
	
	sum=max(sum,maxx1+maxx2+s[x]-1);
//	cout<<x<<' '<<s[x]<<' '<<maxx1<<' '<<maxx2<<' '<<sum<<' '<<maxx1+maxx2+s[x]-1<<endl; 
}
int main()
{
//	freopen("WORM.in","r",stdin);
//	freopen("WORM.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y;
		s[x]++;
		s[y]++;
		add(x,y,1);
		add(y,x,1);
	}
	for(int i=1;i<=n;i++)
	d1[i]=1;
	dfs(1,0);
//	for(int i=1;i<=n;i++)
//	cout<<d1[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<=n;i++)
//	cout<<s[i]<<' ';
//	cout<<endl;
//	for(int i=1;i<=n;i++)
//	cout<<d2[i]<<' ';
//	for(int i=1;i<=n;i++)
//	{
//		sum=max(sum,d1[i]+d2[i]+s[i]);
//	}
	cout<<sum; 
	return 0;
}