题解 | 桃花

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, ans = -1;
vector<int> g[MAXN];
int dfs(int u, int fa = -1) {
    int mx = 1, nmx = 1;
    for(auto &v : g[u]){
        if(v==fa)continue;
        int cur = dfs(v, u);
        if(cur > mx) nmx = mx, mx = cur;
        else if(cur > nmx) nmx = cur;
    }
    ans = max(ans, mx + nmx - 1);
    return mx + 1;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
    cin>>n;
    for(int i=1,u,v; i<n; i++){
        cin>>u>>v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1);
    cout<<ans;
    return 0;
}

答案由一个节点和从该节点伸出的两条链组成

也就是树的直径

递归一次求解

每次寻找上述情况的最大值