Cod sursa(job #465037)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 22 iunie 2010 23:13:25
Problema Dosare Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 16010
#define f first
#define s second

int sol, n;
vector < int> G[nmax];
pair <int, int> v[nmax];

int cmp(int x, int y)
{
	return v[x].s>v[y].s;
}

void dfs(int nod)
{
	if (!G[nod].size()) 
	{
		v[nod].s=0;
		return;
	}
	int i;
	for (i=0; i<G[nod].size(); i++) dfs(G[nod][i]);
	sort(G[nod].begin(), G[nod].end(), cmp);
	int c=0;
	for (i=0; i<G[nod].size(); i++)
	{
		v[nod].f+=v[G[nod][i]].f;
		c++;
		v[nod].s+=c*v[G[nod][i]].f+v[G[nod][i]].s;
	}
}

int main()
{
	freopen("dosare.in","r",stdin);
	freopen("dosare.out","w",stdout);
	scanf("%d",&n);
	int i, x, s=0;
	for (i=2; i<=n; i++)
	{
		scanf("%d",&x);
		G[x].push_back(i);
	}
	for (i=1; i<=n; i++) 
	{
		scanf("%d",&v[i].f);
		s+=v[i].f;
	}
	dfs(1);
	printf("%d\n",v[1].s+s);
}