Pagini recente » Cod sursa (job #2785356) | Cod sursa (job #1713215) | Cod sursa (job #2452444) | Cod sursa (job #705034) | Cod sursa (job #116675)
Cod sursa(job #116675)
Utilizator |
Andrei Grigorean wefgef |
Data |
19 decembrie 2007 11:22:25 |
Problema |
Dosare |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
1.83 kb |
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <functional>
#include <cassert>
using namespace std;
typedef long long LL;
const int MAXN = 16024;
int A[MAXN];
vector<int> adj[MAXN];
//pair<LL, LL> go(int n, int paps) {
// vector<pair<LL, LL> > vp;
// for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
// if (paps == *it) continue;
// vp.push_back(go(*it, n));
// }
//
// sort(vp.begin(), vp.end(), greater<pair<LL, LL> >());
//
// //int S = vp.size();
// //for (int step = 0; step < S; ++step) {
// // bool ok = false;
// // for (int i = 0; i+1 < S; ++i) {
// // if (vp[i] < vp[i+1]) {
// // swap(vp[i], vp[i+1]);
// // ok = true;
// // }
// // }
// // if (!ok) break;
// //}
//
// LL num = A[n], cost = A[n];
// for (int i = 0; i < vp.size(); ++i) cost += vp[i].second + vp[i].first * (i+1), num += vp[i].first;
// return make_pair(num, cost);
//}
pair<LL, LL> go1(int n, int paps) {
vector<pair<LL, LL> > vp;
for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it) {
if (paps == *it) continue;
vp.push_back(go1(*it, n));
}
sort(vp.begin(), vp.end(), greater<pair<LL, LL> >());
LL num = A[n], cost = A[n];
for (int i = 0; i < vp.size(); ++i) cost += vp[i].first + vp[i].second * (i+1), num += vp[i].second;
return make_pair(cost, num);
}
int main() {
freopen("dosare.in", "rt", stdin);
freopen("dosare.out", "wt", stdout);
int N;
scanf("%d", &N);
assert(1 <= N && N <= 16000);
for (int i = 1; i < N; ++i) {
int paps;
scanf("%d", &paps);
assert(1 <= paps && paps <= N);
adj[paps-1].push_back(i);
}
for (int i = 0; i < N; ++i) {
scanf("%d", &A[i]);
assert(A[i] >= 0 && A[i] <= 1000000);
}
pair<LL, LL> res = go1(0, -1);
printf("%lld\n", res.first);
return 0;
}