HihoCoder1050 树中的最长路 树形DP第三题(找不到对象)

题意：求出的树中距离最远的两个结点之间相隔的距离。

水题一道，以前只会用路的直径来解。

代码如下：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<memory>

#include<algorithm>

using namespace std;

const int maxn=;

int dis[maxn],Laxt[maxn],Next[maxn],To[maxn];

int cnt,S,Max;

void add(int u,int v)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

}

void _dfs(int u)

{

    for(int i=Laxt[u];i;i=Next[i]){

        if(!dis[To[i]]){

            dis[To[i]]=dis[u]+;

            if(dis[To[i]]>Max){

                Max=dis[To[i]];

                S=To[i];

            }

            _dfs(To[i]);

        }

    }

}

int main()

{

    int n,i,j,u,v;

    scanf("%d",&n);

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

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

        add(u,v);

        add(v,u);

    }

    dis[]=;S=;Max=;

    _dfs();

    memset(dis,,sizeof(dis));

    dis[S]=;Max=;

    _dfs(S);

    printf("%d\n",Max-);

}

树形DP：

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<memory>

#include<algorithm>

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn];

int dp[maxn],vis[maxn];

int cnt,ans;

void add(int u,int v)

{

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt;

    To[cnt]=v;

}

int _dfs(int u)

{

    for(int i=Laxt[u];i;i=Next[i]){

        if(!vis[To[i]]){

            vis[To[i]]=;

            _dfs(To[i]);

            ans=max(ans,dp[u]+dp[To[i]]+);

            dp[u]=max(dp[u],dp[To[i]]+);

        }

    }

    return dp[u];

}

int main()

{

    int n,i,j,u,v;

    scanf("%d",&n);

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

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

        add(u,v);

        add(v,u);

    }

    vis[]=;

    _dfs();

    printf("%d\n",ans);

    return ;

}