A21511.恋爱 全站第一题解

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long t;
    long long c;
    std::cin >> n >> t >> c;

    std::vector<std::vector<int>> adj(n + 1);
    std::vector<long long> a(n + 1);

    for (int i = 1; i <= n; ++i) {
        int b_i;
        long long a_i;
        std::cin >> b_i >> a_i;
        adj[b_i].push_back(i);
        a[i] = a_i;
    }

    std::vector<long long> dp(n + 1, 0);

    for (int i = n; i >= 1; --i) {
        if (adj[i].empty()) {
            dp[i] = a[i];
        } else {
            std::vector<long long> child_costs;
            child_costs.reserve(adj[i].size());
            for (int child : adj[i]) {
                child_costs.push_back(dp[child]);
            }

            long long num_children = adj[i].size();
            long long required_children = (num_children * a[i] + t - 1) / t;

            if (required_children <= 0) {
                dp[i] = 0;
            } else {
                std::nth_element(child_costs.begin(), child_costs.begin() + required_children - 1, child_costs.end());
                
                long long current_cost = 0;
                for (long long k = 0; k < required_children; ++k) {
                    current_cost += child_costs[k];
                }
                dp[i] = current_cost;
            }
        }
    }

    std::vector<long long> root_child_costs;
    if (!adj[0].empty()) {
        root_child_costs.reserve(adj[0].size());
        for (int child : adj[0]) {
            root_child_costs.push_back(dp[child]);
        }
    }

    long long num_root_children = adj[0].size();
    long long required_root_children = (num_root_children * c + t - 1) / t;

    if (required_root_children <= 0) {
        std::cout << 0 << '\n';
    } else {
        std::nth_element(root_child_costs.begin(), root_child_costs.begin() + required_root_children - 1, root_child_costs.end());
        
        long long final_cost = 0;
        for (long long k = 0; k < required_root_children; ++k) {
            final_cost += root_child_costs[k];
        }
        std::cout << final_cost << '\n';
    }

    return 0;
}