hihocoder 1224 赛车

最新推荐文章于 2017-02-28 02:16:23 发布

_zidaoziyan

最新推荐文章于 2017-02-28 02:16:23 发布

阅读量408

点赞数

分类专栏： hihocoder

本文链接：https://blog.csdn.net/acm_fighting/article/details/48132637

版权

hihocoder 专栏收录该内容

2 篇文章

订阅专栏

本文介绍了一种求解特定树形结构中某节点到根节点的最长路径和次长路径的方法，通过维护节点下的最大路径和次大路径，利用递归深度优先搜索算法实现了路径的高效计算。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

答案必定为某一个结点下面的最长路和次长路再加上该点到根的距离
可以通过维护这一个结点下面的最长距离和最短距离

#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int maxn=100100;
vector<int>G[maxn];
int a[maxn][2]; //维护其子节点 的最大值和次大值
int dp[maxn];   //叶子到该节点的最大深度-1,叶子本身深度为0
int cnt;

void init(int n){
    for(int i=1;i<=n;i++){
        G[i].clear();
    }
}

void dfs(int u,int dep){
    if(G[u].size()==0){
        dp[u]=0;
    }
    else{
        a[u][0]=a[u][1]=-1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i];
            dfs(v,dep+1);
            if(dp[v]>a[u][0]){
                a[u][1]=a[u][0];
                a[u][0]=dp[v];
            }
            else if(dp[v]>a[u][1]){
                a[u][1]=dp[v];
            }
        }
        cnt=max(cnt,a[u][0]+1+a[u][1]+dep+1);
        dp[u]=a[u][0]+1;
    }
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        init(n);
        int u,v;
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        cnt=0;
        dfs(1,0);
        printf("%d\n",cnt);
    }
    return 0;
}