Cod sursa(job #2170919)

Utilizator SenibelanMales Sebastian Senibelan Data 15 martie 2018 10:23:54
Problema Cerere Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream in("cerere.in");
ofstream out("cerere.out");

const int NMAX = 100005;
int N;
int V[NMAX];
vector <int> G[NMAX];
vector <int> tree;
int results[NMAX], T[NMAX];
int root;

void Read(){
    in >> N;
    for(int i = 1; i <= N; ++i)
        in >> V[i];
    for(int i = 1; i <= N - 1; ++i){
        int a, b;
        in >> a >> b;
        G[a].push_back(b);
        T[b] = a;
    }
    // root = 1;
    for(int i = 1; i <= N; ++i){
        if(T[i] == 0){
            root = i;
            break;
        }
    }
}

void DFS(int node){
    if(V[node])
        results[node] = results[tree[tree.size() - V[node]]] + 1;
    tree.push_back(node);
    for(int i = 0; i < G[node].size(); ++i)
        DFS(G[node][i]);
    tree.pop_back();
}

void Print(){
    for(int i = 1; i <= N; ++i)
        out << results[i] << " ";
    out << "\n";
}

int main(){
    Read();
    DFS(root);
    Print();
    return 0;
}