【競プロ典型90問】003 - Longest Circular Road（★4）

概要・感想

解説を見たらなんかdfsを2回やればいいらしい。確かに…。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
vector<int> cand(0);
int n;

int dfs(int s, int p) {
    vector<int> path(1, 0);
    for (auto nxt: graph[s]) {
        if (nxt == p) continue;
        path.push_back(dfs(nxt, s));
    }
    sort(path.begin(), path.end(), greater<int>());
    if (path.size() >= 2) cand.push_back(path[0]+path[1]+1);
    return path[0]+1;
}

int main() {
    cin >> n;
    int a, b;
    graph.resize(n);
    for (int i = 0; i < n-1; i++) {
        cin >> a >> b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }
    dfs(0, -1);
    sort(cand.begin(), cand.end(), greater<int>());
    cout << cand[0] << endl;
}