Cod sursa(job #2476194)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 18 octombrie 2019 11:53:07
Problema Cerere Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#include<vector>
const int NMAX = 100000;
std :: vector<int>v[NMAX + 1];
std :: vector<int>coada;
int viz[NMAX + 1];
int k[NMAX + 1];
int dp[NMAX + 1];
int tata[NMAX + 1];
void dfs(int nod ,int dist)
{
    if(k[nod] == 0);
    else
    dp[nod] = dp[coada[coada.size() - k[nod]]] + 1;
    coada.push_back(nod);
    for(int i = 0 ; i < v[nod].size() ; i ++)
    {
        if(viz[v[nod][i]] == 0 )
        dfs(v[nod][i] , dist + 1);
    }
    coada.pop_back();
}
int main()
{
    freopen("cerere.in" , "r" , stdin);
    freopen("cerere.out" , "w" , stdout);
    int n;
    scanf("%d" , &n);
    for(int i = 1; i <= n ; i ++)
    {
        scanf("%d" , &k[i]);
    }
    for(int i = 1; i < n ; i ++)
    {
        int x , y;
        scanf("%d%d" , &x , &y);
        v[x].push_back(y);
        tata[y] = 1;
    }
    for(int i = 1; i <= n ; i ++)
    {
        if(tata[i] == 0)
        dfs(i , 0);
    }
    for(int i = 1; i <= n ; i ++)
    printf("%d " , dp[i]);
    return 0;
}