Cod sursa(job #857368)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 17 ianuarie 2013 19:18:57
Problema Dosare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax (1<<14)
using namespace std;

vector <int> Arb[Nmax];
long long Sol;
long long N,A[Nmax];

bool cmp(int X,int Y) {
	return A[X]>A[Y];
}
void UpDfs(int Nod) {
	
	for(int i=0;i<Arb[Nod].size();i++) {
		UpDfs(Arb[Nod][i]);
		A[Nod]+=A[Arb[Nod][i]];
		}
	
	sort(Arb[Nod].begin(),Arb[Nod].end(),cmp);
	
}
void DownDfs(int Nod) {
	
	for(int i=0;i<Arb[Nod].size();i++) {
		Sol+=1LL*(i+1)*A[Arb[Nod][i]];
		DownDfs(Arb[Nod][i]);
		}
	
}
void Solve() {
	
	UpDfs(1);
	Sol+=A[1];
	DownDfs(1);
	
}
void Read() {
	
	int i,x;
	ifstream in("dosare.in");
	in>>N;
	
	for(i=2;i<=N;i++) {
		in>>x;
		Arb[x].push_back(i);
		}
	
	for(i=1;i<=N;i++)
		in>>A[i];
	
	in.close();
	
}
void Write() {
	
	ofstream out("dosare.out");
	out<<Sol<<'\n';
	out.close();
	
}
int main() {
	
	Read();
	Solve();
	Write();
	
	return 0;
	
}