Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 300007
- using namespace std;
- typedef long long ll;
- vector <int> v[MAX];
- int size[MAX];
- int cent[MAX];
- bool compare (int x, int y)
- {
- return size[x]>=size[y];
- }
- void sz(int ver)
- {
- if (size[ver]!=0) return;
- if (v[ver].size()==0)
- {
- size[ver]=1;
- return;
- }
- for (int i=0; i<v[ver].size(); i++)
- {
- sz(v[ver][i]);
- }
- for (int i=0; i<v[ver].size(); i++)
- {
- size[ver]+=size[v[ver][i]];
- }
- size[ver]++;
- return;
- }
- int main ()
- {
- int n, q, i, j, k, l, m, x, y;
- cin >> n >> q;
- for (i=0; i<MAX; i++) size[i]=0, cent[i]=0;
- for (i=2; i<=n; i++)
- {
- cin >> x;
- v[x].push_back(i);
- }
- sz(1);
- // for (i=1; i<=n; i++)
- // {
- // cout << size[i] << " ";
- // }
- for (i=1; i<=n; i++)
- {
- sort (v[i].begin(), v[i].end(), compare);
- }
- // for (i=1; i<=n; i++)
- // {
- // for (j=0; j<v[i].size(); j++)
- // {
- // cout << v[i][j] << " ";
- // }
- // cout << endl;
- // }
- int child, par;
- for (i=1; i<=n; i++)
- {
- if (cent[i]!=0) continue;
- if (size[i]<=2)
- {
- cent[i]=i;
- }
- else
- {
- if (size[v[i][0]] <= (size[i]-1)/2)
- {
- cent[i]=i;
- }
- else
- {
- par=i;
- child = v[i][0];
- while (size[child] > (size[i]-1)/2)
- {
- par = child;
- child = v[child][0];
- }
- cent[i]=par;
- }
- }
- }
- // for (i=1; i<=n; i++)
- // {
- // cout << cent[i] << " ";
- // }
- for (i=0; i<q; i++)
- {
- cin >> x;
- cout << cent[x] << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement