[hihocoder 1050]求树的最长链

题目链接：http://hihocoder.com/problemset/problem/1050

两种方法：

1. 两遍dfs，第一次随便找一个根，找到距离这个根最远的点，这个点必然是最长链的一端。第二次就用这个端点做一遍dfs，最远的点就是另一端。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int d[maxn];

vector<int> G[maxn];

void dfs(int u,int fa,int now)

{

    d[u]=now;

    for (int i=;i<G[u].size();i++)

    {

        int v=G[u][i];

        if (v!=fa) dfs(v,u,now+);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    for (int i=;i<n-;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(,,);

    int ma=,maj=;

    for (int i=;i<=n;i++)

    {

        if (d[i]>ma)

        {

            ma=d[i];

            maj=i;

        }

    }

    dfs(maj,,);

    int ans=;

    for (int i=;i<=n;i++) ans=max(ans,d[i]);

    printf("%d",ans);

    return ;

}

2. 树形dp。记dp[i][0/1]表示以i为lca的最长链和次长链的长度，一遍dfs更新就好了。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int dp[maxn][];

vector<int> G[maxn];

void dfs(int u,int fa)

{

    for (int i=;i<G[u].size();i++)

    {

        int v=G[u][i];

        if (v!=fa) dfs(v,u);

    }

    if (G[u].size()<=)

    {

        for (int i=;i<G[u].size();i++)

        {

            int v=G[u][i];

            if (v!=fa) dp[u][]=dp[v][]+;

        }

    }

    else

    {

        for (int i=;i<G[u].size();i++)

        {

            int v=G[u][i];

            if (v!=fa)

            {

                if (dp[v][]+>dp[u][])

                {

                    dp[u][]=dp[u][];

                    dp[u][]=dp[v][]+;

                }

                else dp[u][]=max(dp[v][]+,dp[u][]);

            }

        }

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    G[].push_back();

    for (int i=;i<n-;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dfs(,);

    int ans=;

    for (int i=;i<=n;i++) ans=max(ans,dp[i][]+dp[i][]);

    printf("%d",ans);

    return ;

}

巴特西

[hihocoder 1050]求树的最长链

最新文章

热门文章