1 条题解
-
0Guest LV 0 MOD
-
0
#include<bits/stdc++.h> using namespace std; const int N=300009; vector<int>e[N]; int f[N],ans; void dfs(int u,int fa) { int mx0=0,mx1=0; for(int i=0,v;i<e[u].size();i++) if((v=e[u][i])!=fa){ dfs(v,u); f[u]=max(f[u],f[v]); if(f[v]>mx0) mx1=mx0,mx0=f[v];//mx0最大 mx1 次大 else if(f[v]>mx1) mx1=f[v]; } int cnt=e[u].size()-(fa!=-1);//cnt记录的是孩子结点数 f[u]+=(1+max(0,cnt-1));//这里1指的是结点u,后面的cnt-1,减掉的1指的是v,如果u点是叶子, max(0,cnt-1)就为0 // cout<<"f["<<u<<"]:"<<f[u]<<endl; ans=max(ans,mx0+mx1+1+max(0,cnt-1-(fa==-1))); } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u); dfs(1,-1); printf("%d",ans); return 0; } /* fu为在u的子树中,以u为毛毛虫的头的最大结点个数。 ans=max(ans,mx0+mx1+1+max(0,cnt-1-(fa==-1))); mx0和mx1指的是u的最大子树和次大子树 +1加的是结点u cnt是结点u的孩子结点总数(注意:不包含父结点 本来应该减掉2,即减掉最大和次大的孩子结点 并且因为cnt没有算上父节点,所以如果u的父节点存在的话此处应该在加上父节点, cnt-1-(fa==-1) 表示如果父节点存在,那么 cnt+1-2 相当于就是 cnt-1 而上面的表达式中(fa==-1)正好会返回0, 正好等于cnt-1 而如果父节点不存在,cnt-2 而此时上面表达式中 (fa==-1)正好会返回1, 正好等于cnt-2 */
- 1
信息
- ID
- 1378
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者