@[chen_zhe](/space/show?uid=8457)
by 潜伏者 @ 2018-09-26 10:35:16
@[chen_zhe](/space/show?uid=8457)
by 潜伏者 @ 2018-09-26 21:03:07
的确第一个题解少加了特判(关系不是很大
第二个题解貌似不太对,状态转移没有考虑好什么时候减一,
by chdy @ 2018-12-05 10:02:33
```
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<ctime>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=300002;
int n,m;
int lin[maxn<<1],ver[maxn<<1],nex[maxn<<1],len=0;
int vis[maxn],ru[maxn],ans=0,f[maxn];
void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
void dfs(int x)
{
vis[x]=1;
int v=0,syv=0;
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
if(vis[tn]==0)
{
dfs(tn);
if(f[tn]>syv)
{
if(f[tn]>v)syv=v,v=f[tn];
else syv=f[tn];
}
f[x]=max(f[x],f[tn]+ru[x]-1);//f[tn]+当前节点的度也包括了tn这个点重复了
}
}
ans=max(ans,(v>0?v-1:v)+(syv>0?syv-1:syv)+ru[x]);
//从当前点出发的链如果两条都大于0那说明ru[x]重复了两次
}
int main()
{
freopen("1.in","r",stdin);
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
add(x,y);add(y,x);
ru[x]++;ru[y]++;
}
for(int i=1;i<=n;i++)f[i]=1;
dfs(1);
printf("%d\n",ans+1);//根节点还没算
return 0;
}
```
by chdy @ 2018-12-05 10:03:54
这是我针对第二个题解的改进
by chdy @ 2018-12-05 10:04:09
@[chen_zhe](/space/show?uid=8457)
by chdy @ 2018-12-05 10:05:17
@[chdy](/space/show?uid=59688) 不用特判,初始赋值mx=-2就行
by ecnerwaIa @ 2019-03-22 09:12:18
捕捉神犇 get+1@[千年之狐_天才](/space/show?uid=54113)
by chdy @ 2019-03-22 09:23:36