USACO银牌题目 CSES1131 Tree Diameter (DFS Tree) 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MN=2e5+1;

vector<int> tree[MN];

int diameter=0;

int vis[MN];

int dfs(int x){

    vis[x]=1;

    int l1=-1,l2=-1;

    for(auto y : tree[x]){

        if(vis[y]==0){

            int t=dfs(y);

            if(t>l1){

                l2=l1;

                l1=t;

            }else{

                if(t>l2){

                    l2=t;

                }

            }

        }

    }

    diameter=max(diameter,l1+l2+2);

    return l1+1;

}    

int main()

{

    int n,a,b;

    cin>>n;

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

        cin>>a>>b;

        tree[a].push_back(b);

        tree[b].push_back(a);

    }

    dfs(1);

    cout<<diameter<<endl;        

    return 0;

}