Решение задачи Кефа и парк с Codeforces

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

Кефа решил отпраздновать свой первый крупный заработок походом в ресторан.

Он живет возле необычного парка. Парк представляет из себя подвешенное дерево из n вершин c корнем в вершине 1. В вершине 1 также находится дом Кефы. К сожалению для нашего героя, в парке также находятся коты. Кефа уже выяснил номера вершин, в которых находятся коты.

В листовых вершинах парка находятся рестораны. Кефа хочет выбрать ресторан, в который он пойдет, но, к сожалению, он очень боится котов, поэтому он ни за что не пойдёт в ресторан, на пути к которому от его дома найдётся более m подряд идущих вершин с котами.

Ваша задача — помочь Кефе посчитать количество ресторанов, в которые он может сходить.

Код 

#include<bits/stdc++.h>
using namespace std;

int a[100005],bn=0;

int n,m;

vector<int> ma[100005];

void dfs(int i,int j,int cnt){
    if(a[j])
        cnt++;
    else cnt=0;
    if(cnt>m)
        return;
    if(ma[j].size()==1 && j!=1) bn++;
    for(int k=0;k<ma[j].size();k++)
        if(ma[j][k]!=i)
            dfs(j,ma[j][k],cnt);
}

int main() { 
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    n--;
    while(n--){
        int x,y;
        cin>>x>>y;
        ma[x].push_back(y);
        ma[y].push_back(x);
    }
    dfs(0,1,0);
    cout<<bn;
    return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp