fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. #define maxN 100007
  7. int n;
  8. vector<int>child[maxN];
  9. vector<int>curList;
  10. int sz[maxN];
  11. int ans[maxN];
  12.  
  13. void readData()
  14. {
  15.     cin >> n;
  16.     int p;
  17.     for(int i = 2; i <= n; i++)
  18.     {
  19.         cin >> p;
  20.         child[p].push_back(i);
  21.     }
  22. }
  23.  
  24. void dfs(int u)
  25. {
  26.     sz[u] = 1;
  27.     int v;
  28.     for(int i = 0; i < child[u].size(); i++)
  29.     {
  30.         v = child[u][i];
  31.         dfs(v);
  32.         sz[u] += sz[v];
  33.     }
  34. }
  35.  
  36. void calCentroid()
  37. {
  38.     //for(int i = 0; i < curList.size(); i++)
  39.     //    cout << curList[i] << " ";
  40.     //cout << "\n";
  41.     int j = 0;
  42.     for(int i = 0; i < curList.size(); i++)
  43.     {
  44.         while((curList.size()-j-1)*2>sz[curList[i]])
  45.             j++;
  46.         ans[curList[i]] = curList[j];
  47.     }
  48. }
  49.  
  50. void hld(int u)
  51. {
  52.     curList.push_back(u);
  53.     if(child[u].size() == 0)
  54.     {
  55.         calCentroid();
  56.         curList.clear();
  57.         return;
  58.     }
  59.     int x = 0;
  60.     for(int i = 1; i < child[u].size(); i++)
  61.         if(sz[child[u][i]] > sz[child[u][x]])
  62.             x = i;
  63.     hld(child[u][x]);
  64.     for(int i = 0; i < child[u].size(); i++)
  65.         if(i != x)
  66.             hld(child[u][i]);
  67. }
  68.  
  69. int main()
  70. {
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.     readData();
  75.     dfs(1);
  76.     hld(1);
  77.     for(int i = 1; i <= n; i++)
  78.         cout << ans[i] << "\n";
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5836KB
comments (?)
stdin
copy 
9 
1 
2 
2 
3 
3 
4 
7 
8
stdout
copy 
2
2
3
7
5
6
8
8
9
https://ideone.com/c8NNNK
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!