Cod sursa(job #586038)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 30 aprilie 2011 13:25:50
Problema Guvern Scor 10
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 0.91 kb
#include <algorithm>
#include <vector>

using namespace std;
#define N_MAX 100005

vector <int> a[N_MAX];
int n,x,y;

bool ut[N_MAX];

int euler[N_MAX],fPoz[N_MAX],lPoz[N_MAX],adanc[N_MAX],dim;

int minim[N_MAX],cost[N_MAX];

void df(int nod)
{
	ut[nod]=1;
	
	euler[++dim]=nod;
	fPoz[nod]=dim;
	vector <int> ::iterator it;
	
	minim[nod]=cost[nod];
	for(it=a[nod].begin();it!=a[nod].end();it++)
	{
		if(ut[*it])
			continue;
		
		df(*it);
		
		minim[nod]=max(minim[nod],minim[*it]);
	}
	lPoz[nod]=dim;
}

int sol,i;

int main()
{
	freopen("guvern.in","r",stdin);
	freopen("guvern.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	for(i=1;i<=n;i++)
		scanf("%d",&cost[i]);
	
	df(1);
	
	for(i=1;i<=n;i++)
	{
		if(minim[i]<=cost[i])
			sol++;
	}
	
	printf("%d\n",sol-2);
	
	return 0;
}