Advertisement
Josif_tepe

Untitled

Feb 8th, 2024
670
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <cstring>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 2e5 + 10;
  8. vector<int> graph[maxn];
  9. int subtree[maxn];
  10. int n, m;
  11. void subtree_size(int node, int prev) {
  12.     subtree[node] = 1;
  13.    
  14.     for(int neighbour : graph[node]) {
  15.         if(neighbour != prev) {
  16.             subtree_size(neighbour, node);
  17.             subtree[node] += subtree[neighbour];
  18.         }
  19.     }
  20. }
  21. int centroid(int node, int prev) {
  22.     for(int neighbour : graph[node]) {
  23.         if(neighbour != prev) {
  24.             if(subtree[neighbour] * 2 > n) {
  25.                 return centroid(neighbour, node);
  26.             }
  27.         }
  28.     }
  29.     return node;
  30. }
  31. int main() {
  32.     ios_base::sync_with_stdio(false);
  33.     cin >> n;
  34.     for(int i = 0; i < n - 1; i++) {
  35.         int a, b;
  36.         cin >> a >> b;
  37.         a--; b--;
  38.         graph[a].push_back(b);
  39.         graph[b].push_back(a);
  40.     }
  41.     subtree_size(0, -1);
  42.     cout << centroid(0, -1) + 1 << endl;
  43.     return 0;
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement