Pagini recente » Cod sursa (job #2797329) | Cod sursa (job #2055354) | Cod sursa (job #1323739) | Cod sursa (job #780294) | Cod sursa (job #3149891)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("dosare.in");
ofstream fout("dosare.out");
const int NMAX = 16003;
vector<int> g[NMAX];
int tata[NMAX], f[NMAX], dp[NMAX], c[NMAX];
bool vis[NMAX];
void sortare(vector<int>& v) {
bool ok = false;
int size = (int)v.size();
while (!ok) {
ok = true;
for (int i = 0; i < size - 1; i++) {
int c1 = (i + 1) * dp[v[i]], c2 = (i + 1) * dp[v[i + 1]];
if (c1 > c2) {
ok = false;
int aux = v[i];
v[i] = v[i + 1];
v[i + 1] = aux;
}
}
}
}
bool cmp(const int& a, const int& b) {
return dp[a] > dp[b];
}
void dfs(const int& nod, const int& ind) {
vis[nod] = true;
dp[nod] = ind;
bool frunza = true;
int i = 0;
for (auto fiu : g[nod]) {
if (!vis[fiu]) {
frunza = false;
dfs(fiu, i);
i++;
}
}
if (frunza)
return;
sort(g[nod].begin(), g[nod].end(), cmp);
i = 0;
for (auto fiu : g[nod]) {
dp[nod] += i * dp[fiu];
i++;
}
}
int res = 1;
void calc_cost(const int& nod, const int& cost) {
vis[nod] = true;
int i = 0;
for (auto fiu : g[nod]) {
res += f[fiu] * (cost + i + 1);
//cout << fiu << ' ' << cost + i + 1<< '\n';
calc_cost(fiu, cost + i + 1);
i++;
}
}
int main() {
int n;
fin >> n;
for (int i = 2; i <= n; i++) {
fin >> tata[i];
g[tata[i]].push_back(i);
}
for (int i = 1; i <= n; i++)
fin >> f[i];
dfs(1, 0);
memset(vis, 0, sizeof(vis));
calc_cost(1, 1);
// for (int i = 1; i <= n; i++)
// cout << dp[i] << ' ';
fout << res;
return 0;
}