Pagini recente » Cod sursa (job #2746328) | Cod sursa (job #1626775) | Cod sursa (job #2355669) | Cod sursa (job #2191448) | Cod sursa (job #116668)
Cod sursa(job #116668)
Utilizator |
Andrei Grigorean wefgef |
Data |
19 decembrie 2007 11:05:30 |
Problema |
Dosare |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
1.81 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(go(*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 = go(0, -1);
printf("%lld", res.second);
return 0;
}