Решение задачи "Новогодняя елка" с Codeforces

Без пояснения   Просмотров: 9


Рассмотрим корневое дерево. В корневом дереве есть одна выделенная вершина — корень. Все ребра ориентированы по направлению от корня. Вершина u является ребенком вершины v, а вершина v является родителем вершины u, если существует ориентированное ребро из v в u. Листом корневого дерева называется вершина, у которой нет детей, и есть родитель.

Назовем корневое дерево елкой, если у каждой вершины, не являющейся листом, хотя бы 3 ребенка являются листами. Вам дано корневое дерево, проверьте, является ли оно елкой.


Код

#include <bits/stdc++.h>
using namespace std;
int main(){
     int n,i;
     cin >> n;
     vector<int> p(n + 1), c(n + 1), d(n + 1);
     for(i = 2; i <= n; i++)
        cin>>p[i];
     for(i = 2; i <= n; i++)
        c[p[i]]++;
     for(i = 2; i <= n; i++)
        if(c[i] == 0)
            d[p[i]]++;
     for(i = 1; i <= n; i++)
        if(c[i] and d[i] < 3)
            break;
     cout << (i > n ? "Yes":"No");
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться