1 条题解

  • 0
    @ 2022-07-28 17:52:08
    #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%
上传者