算法

(树形dp) $O(n\log n)$

设 $dp[x]$ 表示让节点 $x$ 给上级发信，需要的花销。如果 $x$ 是叶子节点，则 $dp[x] = a[x]$。
如果 $x$ 是一个非叶子节点，统计它的子节点的花销，按照从小到大的顺序排序，取前几个达到比率即可。

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

const int N = 500010;

int n, t, c;
int a[N];
vector<ll> sons[N];

ll f(ll root) {
    if (sons[root].empty()) {
        return a[root];
    }
    vector<ll> price;
    for (ll i = 0; i < sons[root].size(); ++i) {
        price.push_back(f(sons[root][i]));
    } 
    sort(price.begin(), price.end());
    ll ans = 0;
    ll base;
    if (root == 0) base = c;
    else base = a[root];
    for (int i = 0; i < 1.0 * base * sons[root].size() / t; ++i) {
        ans += price[i];
    }
    return ans;
}

int main() {
    cin >> n >> t >> c;
    for (int i = 1; i <= n; ++i) {
        int b;
        cin >> b >> a[i];
        sons[b].push_back(i);
    }

    cout << f(0) << '\n';

    return 0;
}