求大佬帮忙看看哪错了
查看原帖
求大佬帮忙看看哪错了
164848
vexpaer楼主2020/11/3 23:22
/*
状态设计 dp[i]... 表示以i为根的树中...

流程 1.dfs求深度 2.从深到浅跑 / 1.dfs跑,从子树往回合信息 

https://www.luogu.com.cn/problem/P3174
*/
#include <bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int dp[300009];
int head[300009];
int cnt=0;
struct edge
{
	int to;
	int next;
}a[1000009];
inline void add(int u,int v)
{
	cnt++;
	a[cnt].to=v;
	a[cnt].next=head[u];
	head[u]=cnt;
}
int n,m;
int dfs(int x,int from)
{
	int maxx=0;
	int num=0;
	for(int i=head[x];i;i=a[i].next)
	{
		if(a[i].to!=from) maxx=max(maxx,dfs(a[i].to,x)),num++;
	}
	if(num==0) return 1;
	return maxx+num;
}
int main()
{
	cin>>n>>m;
	int u,v;
	f(i,1,m)
	{
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	cout<<dfs(1,-1)+1;
    return 0;
}
2020/11/3 23:22
加载中...