lessons/参考实现/12-历年真题/洛谷-P8294.cpp

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using int64 = std::int64_t;

namespace {
constexpr int64 INF = std::numeric_limits<int64>::max() / 4;

int n;
std::vector<int64> weight;
std::vector<int> depth;
std::vector<std::vector<int>> children;
std::vector<std::vector<int>> subtree;
std::vector<std::vector<std::pair<int, int>>> states;
std::vector<int64> dp;
std::vector<int64> minimum_one;
std::vector<int64> minimum_two;

int64& value(int first, int second) {
    return dp[static_cast<std::size_t>(first) * (n + 1) + second];
}

void relax(int64& target, int64 candidate) {
    if (candidate < target) target = candidate;
}

void prepare(int vertex) {
    subtree[vertex].push_back(vertex);
    for (int child : children[vertex]) {
        depth[child] = depth[vertex] + 1;
        prepare(child);
        subtree[vertex].insert(subtree[vertex].end(), subtree[child].begin(),
                               subtree[child].end());
    }
    for (int other : subtree[vertex]) {
        states[vertex].push_back({vertex, other});
        if (other != vertex) states[vertex].push_back({other, vertex});
    }
    if (children[vertex].size() == 2) {
        int left = children[vertex][0];
        int right = children[vertex][1];
        for (int u : subtree[left]) {
            for (int v : subtree[right]) {
                states[vertex].push_back({u, v});
                states[vertex].push_back({v, u});
            }
        }
    }
}

void solve_subtree(int vertex) {
    if (children[vertex].empty()) {
        value(vertex, vertex) = weight[vertex];
        return;
    }
    for (int child : children[vertex]) solve_subtree(child);

    if (children[vertex].size() == 1) {
        int child = children[vertex][0];
        for (auto [v, i] : states[child]) {
            relax(value(vertex, v), value(i, v) + weight[vertex]);
            int u = v;
            relax(value(u, vertex), value(u, i) + weight[vertex] *
                  (depth[i] - depth[vertex]) + weight[u]);
        }
        return;
    }

    int left = children[vertex][0];
    int right = children[vertex][1];
    for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF;

    // The outgoing original weight is in one child, and the incoming weight
    // finishes in the other child.
    for (auto [j, k] : states[left]) relax(minimum_one[k], value(j, k));
    for (auto [j, k] : states[right]) relax(minimum_one[k], value(j, k));
    for (auto [i, k] : states[vertex]) {
        if (i != vertex && k != vertex && minimum_one[k] < INF)
            relax(minimum_two[i], weight[i] * (depth[k] - depth[vertex]) +
                  minimum_one[k]);
    }
    for (auto [v, i] : states[left])
        relax(value(vertex, v), weight[vertex] + value(i, v) + minimum_two[i]);
    for (auto [v, i] : states[right])
        relax(value(vertex, v), weight[vertex] + value(i, v) + minimum_two[i]);

    for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF;
    for (auto [j, k] : states[left])
        relax(minimum_one[j], value(j, k) + weight[vertex] *
              (depth[k] - depth[vertex]));
    for (auto [j, k] : states[right])
        relax(minimum_one[j], value(j, k) + weight[vertex] *
              (depth[k] - depth[vertex]));
    for (auto [i, j] : states[vertex]) {
        if (i != vertex && j != vertex && minimum_one[j] < INF)
            relax(minimum_two[i], weight[j] * (depth[i] - depth[vertex]) +
                  minimum_one[j]);
    }
    for (auto [u, i] : states[left])
        relax(value(u, vertex), weight[u] + value(u, i) + minimum_two[i]);
    for (auto [u, i] : states[right])
        relax(value(u, vertex), weight[u] + value(u, i) + minimum_two[i]);

    for (int x : subtree[vertex]) minimum_one[x] = minimum_two[x] = INF;
    for (auto [u, i] : states[left]) {
        relax(minimum_one[u], value(u, i) + weight[vertex] *
              (depth[i] - depth[vertex]) + weight[u]);
        relax(minimum_two[i], value(u, i));
    }
    for (auto [u, i] : states[right]) {
        relax(minimum_one[u], value(u, i) + weight[vertex] *
              (depth[i] - depth[vertex]) + weight[u]);
        relax(minimum_two[i], value(u, i));
    }
    for (auto [u, v] : states[vertex]) {
        if (u != vertex && v != vertex)
            relax(value(u, v), minimum_one[u] + minimum_two[v]);
    }
}
}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;
    weight.assign(n + 1, 0);
    depth.assign(n + 1, 0);
    children.assign(n + 1, {});
    subtree.assign(n + 1, {});
    states.assign(n + 1, {});
    minimum_one.assign(n + 1, INF);
    minimum_two.assign(n + 1, INF);
    dp.assign(static_cast<std::size_t>(n + 1) * (n + 1), INF);
    for (int i = 1; i <= n; ++i) std::cin >> weight[i];
    for (int i = 2; i <= n; ++i) {
        int parent;
        std::cin >> parent;
        children[parent].push_back(i);
    }
    if (n == 1) {
        std::cout << 0 << '\n';
        return 0;
    }

    prepare(1);
    for (int child : children[1]) solve_subtree(child);

    int64 answer = INF;
    if (children[1].size() == 1) {
        int child = children[1][0];
        for (auto [u, v] : states[child])
            relax(answer, value(u, v) + weight[1] * (depth[v] - depth[1]));
    } else {
        int first_child = children[1][0];
        int second_child = children[1][1];
        for (int direction = 0; direction < 2; ++direction) {
            std::fill(minimum_one.begin(), minimum_one.end(), INF);
            std::fill(minimum_two.begin(), minimum_two.end(), INF);
            for (auto [i, j] : states[first_child])
                relax(minimum_one[i], value(i, j) + weight[1] *
                      (depth[j] - depth[1]));
            for (auto [k, l] : states[second_child])
                relax(minimum_two[l], value(k, l));
            for (auto [i, l] : states[1]) {
                if (i != 1 && l != 1)
                    relax(answer, minimum_one[i] + minimum_two[l] +
                          weight[i] * (depth[l] - depth[1]));
            }
            std::swap(first_child, second_child);
        }
    }
    std::cout << answer << '\n';
    return 0;
}