Advertisement
Guest User

Untitled

a guest
Jun 24th, 2016
357
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 300007
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. vector <int> v[MAX];
  9.  
  10. int size[MAX];
  11. int cent[MAX];
  12.  
  13. bool compare (int x, int y)
  14. {
  15.     return size[x]>=size[y];
  16. }
  17.  
  18. void sz(int ver)
  19. {
  20.     if (size[ver]!=0) return;
  21.     if (v[ver].size()==0)
  22.     {
  23.         size[ver]=1;
  24.         return;
  25.     }
  26.     for (int i=0; i<v[ver].size(); i++)
  27.     {
  28.         sz(v[ver][i]);
  29.     }
  30.     for (int i=0; i<v[ver].size(); i++)
  31.     {
  32.         size[ver]+=size[v[ver][i]];
  33.     }
  34.     size[ver]++;
  35.     return;
  36. }
  37.  
  38. int main ()
  39. {
  40.     int n, q, i, j, k, l, m, x, y;
  41.     cin >> n >> q;
  42.     for (i=0; i<MAX; i++) size[i]=0, cent[i]=0;
  43.     for (i=2; i<=n; i++)
  44.     {
  45.         cin >> x;
  46.         v[x].push_back(i);
  47.     }
  48.     sz(1);
  49. //    for (i=1; i<=n; i++)
  50. //    {
  51. //        cout << size[i] << " ";
  52. //    }
  53.     for (i=1; i<=n; i++)
  54.     {
  55.         sort (v[i].begin(), v[i].end(), compare);
  56.     }
  57. //    for (i=1; i<=n; i++)
  58. //    {
  59. //        for (j=0; j<v[i].size(); j++)
  60. //        {
  61. //            cout << v[i][j] << " ";
  62. //        }
  63. //        cout << endl;
  64. //    }
  65.     int child, par;
  66.     for (i=1; i<=n; i++)
  67.     {
  68.         if (cent[i]!=0) continue;
  69.  
  70.         if (size[i]<=2)
  71.         {
  72.             cent[i]=i;
  73.         }
  74.         else
  75.         {
  76.             if (size[v[i][0]] <= (size[i]-1)/2)
  77.             {
  78.                 cent[i]=i;
  79.             }
  80.             else
  81.             {
  82.                 par=i;
  83.                 child = v[i][0];
  84.                 while (size[child] > (size[i]-1)/2)
  85.                 {
  86.                     par = child;
  87.                     child = v[child][0];
  88.                 }
  89.                 cent[i]=par;
  90.             }
  91.         }
  92.     }
  93. //    for (i=1; i<=n; i++)
  94. //    {
  95. //        cout << cent[i] << " ";
  96. //    }
  97.     for (i=0; i<q; i++)
  98.     {
  99.         cin >> x;
  100.         cout << cent[x] << endl;
  101.     }
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement