hihocoder 1224 賽車

答案必定為某一個結點下面的最長路和次長路再加上該點到根的距離

可以通過維護這一個結點下面的最長距離和最短距離

#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=;
vector<int>G[maxn];
int a[maxn][]; //維護其子節點 的最大值和次大值
int dp[maxn];   //葉子到該節點的最大深度-1,葉子本身深度為0
int cnt;

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

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

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