记录编号	617998	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	T4	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	1.591 s
提交时间	2026-08-25 16:52:11	内存使用	18.04 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int M = (N << 2);
const ll V = 1e9;
const ll inf = 1e18;
/* ---------------------------------- */ 
int n, ver[N], to[N << 1], nxt[N << 1], idx;
ll C, val[N << 1], s[N], f[N], h[N], g[N];
/* ----------------------------------*/
ll k[M], b[M], tag[M];
int rt[N], lc[M], rc[M], cnt, mx[M];
ll calc(int i, ll x) {
    return k[i] * x + b[i];
}
void maketag(int p, ll v) {
    b[mx[p]] += v;
    tag[p] += v;
}
void pushdown(int p) {
    if (!tag[p]) return;
    if (lc[p]) maketag(lc[p], tag[p]);
    if (rc[p]) maketag(rc[p], tag[p]);
    tag[p] = 0; return;
}
void upd(int &p, ll l, ll r, int x) {
    if (!p) p = ++cnt;
    if (!mx[p]) { mx[p] = x; return; }
    pushdown(p); ll mid = (l + r) >> 1;
    if (calc(mx[p], mid) > calc(x, mid)) swap(mx[p], x);
    if (calc(mx[p], l) > calc(x, l)) upd(lc[p], l, mid, x);
    if (calc(mx[p], r) > calc(x, r)) upd(rc[p], mid + 1, r, x);
}
ll ask(int p, ll l, ll r, ll x) {
    if (!p || !mx[p]) return inf;
    pushdown(p); ll mid = (l + r) >> 1;
    ll cnt = calc(mx[p], x);
    if (l == r) return cnt;
    if (x <= mid) cnt = min(cnt, ask(lc[p], l, mid, x));
    if (x > mid) cnt = min(cnt, ask(rc[p], mid + 1, r, x));
    return cnt; 
}
int merge(int p, int q, ll l, ll r) {
    if (!p || !q) return p + q;
    if (mx[q]) upd(p, l, r, mx[q]);
    if (l == r) return 0;
    ll mid = (l + r) >> 1; 
    pushdown(p); pushdown(q);
    lc[p] = merge(lc[p], lc[q], l, mid);
    rc[p] = merge(rc[p], rc[q], mid + 1, r);
    return p;
}
/* ----------------------------------*/ 
void add(int x, int y, int z) {
    to[++idx] = y, nxt[idx] = ver[x], ver[x] = idx, val[idx] = z;
}
void dfs(int x) {
    for (int i = ver[x], y; i; i = nxt[i]) {
        y = to[i];
        s[y] = s[x] + val[i];
        dfs(y);
        h[x] += f[y];
    }
    for (int i = ver[x], y; i; i = nxt[i]) {
        y = to[i];
        g[y] = h[x] - f[y];
        maketag(rt[y], g[y]); 
        rt[x] = merge(rt[x], rt[y], -V, V);
    }
    f[x] = min(h[x] + C, ask(rt[x], -V, V, 2 * s[x]) + s[x] * s[x] + C);
    k[x] = -s[x], b[x] = s[x] * s[x] + h[x];
    upd(rt[x], -V, V, x);
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> C;
    memset(f, 0x3f, sizeof(f));
    for (int i = 2, fa, dis; i <= n; i++) {
        cin >> fa >> dis;
        add(fa, i, dis);
    }
    dfs(1);
    cout << f[1] << '\n';
    return 0;
}