Untitled

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector graph[maxn];
bool mark_centroid[maxn];
int n;
void subtree_dfs(int node, vector & visited, vector & subtree_size, int & cnt_nodes) {
    visited[node] = true;
    subtree_size[node] = 1;
    cnt_nodes++;
    for(int neighbour : graph[node]) {
        if(!visited[neighbour] and !mark_centroid[neighbour]) {
            subtree_dfs(neighbour, visited, subtree_size, cnt_nodes);
            subtree_size[node] += subtree_size[neighbour];
        }
    }
}
int find_centroid(int node, vector & visited, vector & subtree_size, int & cnt_nodes) {
    bool is_centroid = true;
    visited[node] = true;
    int child = 0;
    for(int neighbour : graph[node]) {
        if(!visited[neighbour] and !mark_centroid[neighbour]) {
            if(subtree_size[neighbour] > n / 2) {
                is_centroid = false;
            }
            if(child == 0 or subtree_size[neighbour] > subtree_size[child]) {
                child = neighbour;
                
            }
        }
    }
    if(is_centroid and cnt_nodes - subtree_size[node] <= n / 2) {
        return node;
    }
    return find_centroid(child, visited, subtree_size, cnt_nodes);
}
int centroid(int node) {
    int cnt_nodes = 0;
    vector visited(n + 10, false);
    vector subtree_size(n + 10, 0);
    subtree_dfs(1, visited, subtree_size, cnt_nodes);
    for(int i = 0; i < n + 10; i++) {
        visited[i] = false;
    }
    int cent = find_centroid(node, visited, subtree_size, cnt_nodes);
    mark_centroid[cent] = true;
    return cent;
}
vector cent_tree[maxn];
int centoroid_decomposition(int node) {
    int cent = centroid(node);
    cout << cent << " ";
    for(int neighbour : graph[cent]) {
        if(!mark_centroid[neighbour]) {
            int subtree = centoroid_decomposition(neighbour);
            
            cent_tree[cent].push_back(subtree);
            cent_tree[subtree].push_back(cent);
            
        }
    }
    return cent;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    memset(mark_centroid, false, sizeof mark_centroid);
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cout << centoroid_decomposition(1) << endl;
    return 0;
}
/*
 16
 1 4
 2 4
 3 4
 4 5
 5 6
 6 7
 7 8
 7 9
 6 10
 10 11
 11 12
 12 13
 12 14
 13 15
 13 16
 **/