P3174 [HAOI2009] 毛毛虫,过不了hack数据#11
  • 板块学术版
  • 楼主SpreadWings
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/3 15:57
  • 上次更新2023/10/27 04:25:34
查看原帖
P3174 [HAOI2009] 毛毛虫,过不了hack数据#11
655425
SpreadWings楼主2022/11/3 15:57

如题,求调

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int M=6e5+10;
struct Edge{
	int to,next;
}g[M];
int head[N],cnt;
void addEdge(int from,int to){
	cnt++;
	g[cnt].to=to;g[cnt].next=head[from];head[from]=cnt;
	return ;
}
int n,m;
int val[N];
int mx[N],L;
void dp(int x,int pre){
	mx[x]=val[x];
	for(int i=head[x],y;i;i=g[i].next){
		y=g[i].to;if(y==pre)continue;
		dp(y,x);
		if(L<mx[x]+mx[y])L=mx[x]+mx[y];
		if(mx[x]<mx[y]+val[x])mx[x]=mx[y]+val[x];
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,ui,vi;i<=m;i++){
		scanf("%d%d",&ui,&vi);
		addEdge(ui,vi);addEdge(vi,ui);
		val[vi]++;val[ui]++;
	}
	for(int i=1;i<=n;i++)val[i]--;
	dp(1,1);
	printf("%d",L+2);
	return 0;
}

2022/11/3 15:57
加载中...