社区讨论

RE求助(玄关)

P3174[HAOI2009] 毛毛虫参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m3u0gokk
此快照首次捕获于
2024/11/23 18:12
去年
此快照最后确认于
2025/11/04 14:05
4 个月前
查看原帖
打的树的直径,感觉没啥问题的代码RE了。在本地也过不了n=300000的数据,但把栈空间开大之后就能过,所以我推测是爆栈了。但第二篇的题解也是两边dfs,而且我们两个遍历的方式也大差不差,求大佬们帮一下。
CPP
#include<bits/stdc++.h>
#define int long long
#define int1 register int
using namespace std;
const int maxn=3e6+1e1;
int q[maxn];
int ans1,ans2;
vector<int > a[maxn];
int du[maxn];
int n,m;
int cnt1,cnt2;
int ans;
inline void dfs1(int x,int fa,int sum){
	if(du[x]==1&&fa!=-1){
		if(sum>cnt1) ans1=x,cnt1=sum;
		return ;
	}
	for(int1 v:a[x])
		if(v!=fa)
			dfs1(v,x,sum+1);
}
inline void dfs2(int x,int fa,int sum){
	if(du[x]==1&&fa!=-1){
		if(sum>cnt2) ans2=x,cnt2=sum;
		return ;
	}
	for(int1 v:a[x])
		if(v!=fa)
			dfs2(v,x,sum+1);
}
inline bool work(int x,int fa,int sum){
	if(x==ans2) return true;
	for(int1 v:a[x]){
		bool flag=false;
		if(v!=fa&&work(v,x,sum+1)){
			q[sum]=x;	
			return true;		
		}
	}
}
signed main(){
//	freopen("1.in","r",stdin);
	scanf("%lld%lld",&n,&m);
	while(m--){
		int u,v;
		scanf("%lld %lld",&u,&v);
		du[u]++;du[v]++;
		a[u].push_back(v);a[v].push_back(u);
	}
	dfs1(1,-1,0);
	dfs2(ans1,-1,0);
	bool fuck=work(ans1,-1,0);
	q[cnt2]=ans2;
	for(int i=0;i<=cnt2;i++)
		ans+=du[q[i]];
	ans=ans-cnt2+1;
	printf("%lld\n",ans);
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...