Cod sursa(job #35816)

Utilizator damaDamaschin Mihai dama Data 22 martie 2007 16:11:22
Problema Cerere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <stdio.h>
#include <vector>

using namespace std;

int n, d[100001], sol[100001], used[100001], back[100001], cnt, deg[100001];
vector < int >v[100001];

void dfs(int nod);

int main()
{
	freopen("cerere.in", "r", stdin);
	freopen("cerere.out", "w", stdout);

	int i, a, b;

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)
	{
		scanf("%d", &d[i]);
	}

	for (i = 1; i < n; ++i)
	{
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		++deg[b];
	}
	for(i = 1; i <= n; ++i)
		if(!deg[i])
			dfs(i);

	for (i = 1; i < n; ++i)
		printf("%d ", sol[i]);
	printf("%d\n", sol[n]);
	return 0;
}

void dfs(int nod)
{
	int i;

	used[nod] = 1;
	back[++cnt] = nod;

	if (!d[nod]) {
		sol[nod] = 0;
	} else {
		sol[nod] = sol[back[cnt - d[nod]]] + 1;
	}

	for (i = 0; i < v[nod].size(); ++i) {
		if (!used[v[nod][i]]) {
			dfs(v[nod][i]);
		}
	}
	--cnt;
}