hihoCoder week11 树中的最长路

题目链接： https://hihocoder.com/contest/hiho11/problem/1

求树中节点对 距离最远的长度

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

int n;

vector<int> G[N];

int d[N];

void dfs(int u, int fa)

{

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

        int v = G[u][i];

        if(v != fa) {

            d[v] = d[u] + ;

            dfs(v, u);

        }

    }

}

int main()

{

    freopen("in.txt", "r", stdin);

    scanf("%d",&n);

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

        int a,b; scanf("%d %d", &a, &b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    d[] = ;

    dfs(, );

    int mx =  ;

    int index = -;

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

        if(mx < d[i]) {

            mx = d[i];

            index = i;

        }

    }

    //printf("%d\n", mx);

    memset(d,,sizeof(d));

    dfs(index, );

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

        if(mx < d[i]) {

            mx = d[i];

            index = i;

        }

    }

    cout << mx <<endl;

    return ;

}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + ;

vector<int> G[N];

int n, ans;

int dfs(int u,int fa)

{

    int l1=-,l2=-;

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

        int v = G[u][i];

        if(v == fa) continue;

        int l = dfs(v, u);

        if(l > l1)

            l2=l1 , l1=l;

        else

            l2 = max(l2, l);

    }

    //cout << u <<" "<< l1 <<" "<< l2 <<endl;

    ans = max(ans , l1 + l2 + );

    // cout << u <<" 最长的路为" <<l1 <<endl;

    return l1+;

}

int main()

{

    //freopen("in.txt", "r", stdin);

    cin >> n;

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

        int a,b; scanf("%d %d", &a, &b);

        G[a].push_back(b);

        G[b].push_back(a);

    }

    ans = ;

    dfs(,);

    cout << ans <<endl;

    return ;

}