fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> tree [100001];
  5. vector<int> killed(100001,0);
  6. vector<bool> used(100001,0);
  7. vector<int> dist(100001,0);
  8. int ans=0;
  9.  
  10. void kills(int v,int p)
  11. {
  12.     if(v==p) kills(tree[v][0],v);
  13.     if(tree[v].size()==2) for(auto to:tree[v]) if(to!=p) kills(to,v);
  14.     if(tree[v].size()>=3) killed[v]++;
  15.     return;
  16. }
  17.  
  18. void goup(int v, int p)
  19. {
  20.     if(v==p)
  21.     {
  22.         for(auto to:tree[v]) if(dist[to]<dist[v]) goup(to,v);
  23.         killed[v]=0;
  24.         return;
  25.     }
  26.     if(tree[v].size()==2) for(auto to:tree[v]) if(to!=p) goup(to,v);
  27.     if(tree[v].size()>=3)
  28.     {
  29.         killed[v]++;
  30.         return;
  31.     }
  32. }
  33.  
  34.  
  35. int main()
  36. {
  37.     int n,v; cin>>n;
  38.     if(n<=5) {cout<<1; return 0;} // Частный случай
  39.     tree[1].push_back(0); // Корень тоже должен быть "развилкой"
  40.     vector<int> leaves;
  41.     for(int i=1;i<n;i++)
  42.     {
  43.         cin>>v;
  44.         tree[v].push_back(i+1);
  45.         tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают
  46.     }
  47.  
  48.     for(int i=1;i<=n;i++)
  49.     {
  50.         if(tree[i].size()==1 || (i==1 && tree[i].size()==2)) leaves.push_back(i); //Запоминаем все листья
  51.     }
  52.  
  53.     queue<int> q; dist[1]=0;
  54.     q.push(1); used[1] = true;
  55.     while(!q.empty())
  56.     {
  57.         int qv=q.front(); q.pop();
  58.         used[qv]=1;
  59.         for(auto to:tree[qv])                //BFS заполняющий вектор dist
  60.         {
  61.             if(!used[to])
  62.             {
  63.                 q.push(to);
  64.                 dist[to]=dist[qv]+1;
  65.             }
  66.         }
  67.     }
  68.  
  69.     for(auto l:leaves)
  70.     {
  71.         kills(l,l);        // Первый этап - запросы от каждого листа
  72.     }
  73.  
  74.     int maxdist=-1; for(int i=1;i<=n;i++) maxdist=max(maxdist,dist[i]); // Определение максимального "уровня" дерева
  75.     int wentup=1;
  76.     while(wentup)
  77.     {
  78.         wentup=0;
  79.         for(int l=maxdist;l>0;l--)
  80.         {
  81.             for(int i=2;i<=n;i++)
  82.             {
  83.                 if(killed[i]==1 && dist[i]==l)
  84.                 {
  85.                     goup(i,i);                    //Этап 2 - поднятие "недошедших" запросов
  86.                     wentup++;
  87.                 }
  88.             }
  89.         }
  90.     }
  91.     for(int i=1;i<=n;i++) {if(killed[i]>=2) ans++;} //Финальный подсчет "отравленных" развилок
  92.     cout<<ans;
  93.     return 0;
  94. }
Success #stdin #stdout 0s 6288KB
comments (?)
stdin
copy 
8
1 1 2 1 2 3 2
stdout
copy 
2
https://ideone.com/QpDsws
Убить всех термитов
language:
C++ (gcc 8.3)
created:
4 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!