树的重心非递归做法

#include <iostream>
#include <vector>
#include <stack>
#include <climits>
using namespace std;
const int MAXN = 100010;
vector<int> adj[MAXN];
int sz[MAXN];
int n;
vector<int> centers;
void getSize() {
    stack<pair<int, int>> st;
    stack<bool> vis;
    st.push({1, -1});
    vis.push(false);
    while (!st.empty()) {
        auto [u, fa] = st.top();
        bool isVisited = vis.top();
        st.pop();
        vis.pop();
        if (isVisited) {
            sz[u] = 1;
            for (int v : adj[u]) {
                if (v != fa) sz[u] += sz[v];
            }
        } else {
            st.push({u, fa});
            vis.push(true);
            for (int v : adj[u]) {
                if (v != fa) {
                    st.push({v, u});
                    vis.push(false);
                }
            }
        }
    }
}
void getCentroid() {
    getSize();
    int minMax = INT_MAX;
    centers.clear();
    stack<pair<int, int>> st;
    st.push({1, -1});
    while (!st.empty()) {
        auto [u, fa] = st.top();
        st.pop();
        int maxPart = 0;
        for (int v : adj[u]) {
            if (v != fa) {
                maxPart = max(maxPart, sz[v]);
                st.push({v, u});
            }
        }
        maxPart = max(maxPart, n - sz[u]);
        if (maxPart < minMax) {
            minMax = maxPart;
            centers.clear();
            centers.push_back(u);
        } else if (maxPart == minMax) {
            centers.push_back(u);
        }
    }
}
int main() {
    cin >> n;    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    getCentroid();
    for (int x : centers) cout << x << " ";
    cout << endl;
    return 0;
}