Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cstring>
- #include <fstream>
- #include <algorithm>
- #include <map>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- vector<int> graph[maxn];
- bool mark_centroid[maxn];
- int n;
- void subtree_dfs(int node, vector<bool> & visited, vector<int> & 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<bool> & visited, vector<int> & 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<bool> visited(n + 10, false);
- vector<int> 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<int> 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
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement