题解 | #图的遍历#

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], idx, n;
int d[N];
int maxd[N];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == fa)   continue;
        dfs(j, u);
        maxd[u] = max(maxd[u], maxd[j] + 1);
        d[u] = d[u] + d[j] + 1;
    }
}
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1, -1);
//    for(int i=1;i<=n;++i)
//        cout<<d[i]<<"===>"<<maxd[i]<<endl;
    cout << maxd[1] + 2 * (d[1] - maxd[1]) << endl;
    return 0;
}