Cod sursa(job #2647096)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 3 septembrie 2020 09:18:54
Problema Dosare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <fstream>
#include <algorithm>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

std::ifstream in ("dosare.in");
std::ofstream out ("dosare.out");

ll dfs(int node, std::vector<std::vector<int>> &g, std::vector<ll> &weight, int acc) {
  std::vector<ll> aux;
  ll result = acc * weight[node];

  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    result += dfs(to, g, weight, acc + 1);
    aux.push_back(weight[to]);
    weight[node] += weight[to];
  }

  std::sort(aux.begin(), aux.end());
  std::reverse(aux.begin(), aux.end());
  for(int i = 0; i < aux.size(); i++)
    result += aux[i] * i;
  return result;
}

ll solve(int n, std::vector<std::vector<int>> g, std::vector<ll> weight) {
  return dfs(1, g, weight, 1);
}

int main() {
  int n;
  in >> n;
  std::vector<std::vector<int>> g(1 + n);
  for(int i = 2; i <= n; i++) {
    int far;
    in >> far;
    g[far].push_back(i);
  }
  std::vector<ll> weight(1 + n);
  for(int i = 1; i <= n; i++)
    in >> weight[i];
  out << solve(n, g, weight);
  return 0;
}