题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

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

const int N = 200000 + 10;

int n;
vector<int> g[N];

void add(int a, int b) {
    g[a].push_back(b);
}

int Max = -1;

int dis[N][3];
int hson[N];

void dfs1(int u, int fa = -1) {
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        if (dis[v][0] + 1 > dis[u][0]) {
            dis[u][1] = dis[u][0];
            dis[u][0] = dis[v][0] + 1;
            hson[u] = v;
        } else if (dis[v][0] + 1 > dis[u][1]) dis[u][1] = dis[v][0] + 1;
    }
    Max = max(Max, dis[u][0] + dis[u][1]);
}

void dfs2(int u, int fa = -1) {
    for (auto v : g[u]) {
        if (v == fa) continue;
        dis[v][2] = dis[u][2] + 1;
        if (v == hson[u]) dis[v][2] = max(dis[v][2], dis[u][1] + 1);
        else dis[v][2] = max(dis[v][2], dis[u][0] + 1);
        dfs2(v, u);
    }
}

signed main() {
    cin >> n;
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs1(0);
    dfs2(0);
    for (int i = 0; i <= n; i ++ ) {
        // cout << dis[i][0] << " " << dis[i][1] << " " << dis[i][2] << "\n";
        if (dis[i][0] + dis[i][1] + dis[i][2] - min({dis[i][0], dis[i][1], dis[i][2]}) == Max)
            cout << i << "\n";
    }
    return 0;
}