Pagini recente » Cod sursa (job #1927103) | Cod sursa (job #1615334) | Cod sursa (job #895609) | Cod sursa (job #2639436) | Cod sursa (job #3260057)
#include <fstream>
#include <vector>
#include <algorithm> // sort
using namespace std;
ifstream fin("dosare.in");
ofstream fout("dosare.out");
int n, ans, dp[16005]; // dp[i] - nr total de accesari in subarborele cu radacina i
int moves[16005];
vector<int> G[16005];
void dinamica(int nod) {
for(auto i : G[nod]) {
dinamica(i);
dp[nod] += dp[i];
}
// Construiesc arborele astfel incat sa am cat mai in stanga
// Cat mai multe foldere, pentru a avea nr minim de reveniri
sort(G[nod].begin(), G[nod].end(), [](int x, int y) {
return dp[x] > dp[y];
});
}
// Calculez mutarile cu reveniri
// De exemplu daca mai intai parcurg subarborele stang
// Contorizez si revenirea la radacina plus move-ul catre subarorele drept
void dfs(int nod, int currentMoves) {
ans += moves[nod] * currentMoves;
for(int i = 0; i < G[nod].size(); ++i) {
dfs(G[nod][i], i + currentMoves + 1);
}
}
int main() {
fin >> n;
for(int i = 2; i <= n; ++i) {
int x;
fin >> x;
G[x].push_back(i);
}
for(int i = 1; i <= n; ++i) {
int x;
fin >> x;
dp[i] = moves[i] = x;
}
dinamica(1);
dfs(1, 1); // Apas enter prima oara, deci 1 move
fout << ans;
return 0;
}