社区讨论
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 条回复,欢迎继续交流。
正在加载回复...