fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1000001;
  5.  
  6. int n;
  7. int p[MAX];
  8. int ans[MAX][2];
  9. vector<int> adj[MAX];
  10.  
  11. void dfs_up(int u) {
  12.   while(u != 0) {
  13.     ans[u][0] = 0;
  14.     ans[u][1] = 1;
  15.     for(auto v : adj[u]) {
  16.       ans[u][0] += ans[v][1];
  17.       ans[u][1] += min(ans[v][0], ans[v][1]);
  18.     }
  19.     u = p[u];
  20.   }
  21. }
  22.  
  23. int main() {
  24.   #ifndef ONLINE_JUDGE
  25.     freopen("inp.txt", "r", stdin);
  26.   #endif
  27.   ios_base::sync_with_stdio(false);
  28.   int t;
  29.   cin >> t;
  30.   while(t--) {
  31.     cin >> n;
  32.     for(int i = 1; i <= n; ++i) {
  33.       adj[i].clear();
  34.     }
  35.     for(int i = 2; i <= n; ++i) {
  36.       cin >> p[i];
  37.       adj[p[i]].push_back(i);
  38.       dfs_up(i);
  39.       int animals = i > 3 ? max(2, min(ans[1][0], ans[1][1])) : 1;
  40.       cout << (animals + 1) << " ";
  41.     }
  42.     cout << "\n";
  43.   }
  44.   return 0;
  45. }
Success #stdin #stdout 0.02s 26520KB
comments (?)
stdin
copy 
2
7
1 1 2 2 3 5
16
1 1 2 2 3 3 4 4 5 6 6 6 1 11 11
stdout
copy 
2 2 3 3 3 4 
2 2 3 3 3 3 4 4 5 6 6 6 6 7 7
https://ideone.com/3iqip4
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!