求助(码量少)
查看原帖
求助(码量少)
152980
Euclid楼主2021/11/13 16:36

最后两个点不知道怎么错了

#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5,inf = 1e9 + 7;

int n,m;
int dp1[maxn],dp2[maxn],siz[maxn],tot[maxn];

struct sm
{
    int v,next;
}a[maxn];

int head[maxn],cnt;

void add(int u,int v)
{
    a[++cnt].v = v;
    a[cnt].next = head[u];
    head[u] = cnt;
}

int max(int x,int y)
{
    return x>y?x:y;
}

void dfs(int u,int fa)
{
    int mx1 = -inf,mx2 = -inf;
    for(int i = head[u];i;i = a[i].next)
    {
        int v = a[i].v;
        if(v==fa)continue;
        tot[u]++;
        dfs(v,u);
        if(dp1[v] > mx1)
        {
            mx2 = mx1;
            mx1 = dp1[v];
        }
        else if(dp1[v] > mx2)mx2 = dp1[v];
    }
    if(!tot[u])dp1[u] = dp2[u] = 1;
    else 
    {
        dp1[u] = mx1 + tot[u];
        if(mx2!=-inf)dp2[u] = mx1 + mx2 + tot[u] - 1;
        if(fa!=0)dp2[u]++;
    }
/*  cout<<u<<" "<<mx1<<" "<<mx2<<endl;
    cout<<dp1[u]<<" "<<dp2[u]<<endl;
    cout<<endl;*/
}

signed main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i = 1;i < n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    //dfs2(1,0);
    int ans = -inf;
    for(int i = 1;i <= n;i++)
        ans = max(ans,max(dp1[i],dp2[i]));
    printf("%d",ans);
    return 0;
}

  
2021/11/13 16:36
加载中...