rt，思路是线段树套李超树（不撤销）+出栈序，wa 61pts，写的比较ρ米山

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repr(i, x, y) for (int i = x; i >= y; i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
typedef long long ll;
const int NR = 2e5 + 5;
const int T = 1e6;
const ll INF = 2e18;
int n, lyymcl;
vector<pair<int, ll> > e[NR];
struct City{
    int fa;
    ll p, q, l;
    ll dep;
    int pos;
}c[NR];
int outid;
ll f[NR];
int g[NR][20]; ll h[NR][20];
void dfs0(int u, ll d, ll w){
    c[u].dep = d;
    g[u][0] = c[u].fa;
    h[u][0] = w;
    rep(j, 1, 18){
        g[u][j] = g[g[u][j - 1]][j - 1];
        h[u][j] = h[u][j - 1] + h[g[u][j - 1]][j - 1];
    }
    for (auto kv : e[u]){
        int v = kv.first; ll w = kv.second;
        if (v != c[u].fa){
            dfs0(v, d + w, w);
        }
    }
    c[u].pos = ++outid;
}
struct Line{
    ll k, b;
}line[NR];
int tot;
struct LCT{
    int id;
    int ls, rs;
    int l, r;
}t[20 * NR];
int nodecnt;
int newnode(int id, int ls, int rs, int l, int r){
    t[++nodecnt] = (LCT){id, ls, rs, l, r};
    return nodecnt;
}
bool check(Line x, Line y, int pos){
    return 1ll * pos * x.k + x.b < 1ll * pos * y.k + y.b;
}
void modify(int p, int v){
    if (t[p].id == 0){
        t[p].id = v;
        return;
    }
    if (t[p].l == t[p].r){
        if (check(line[v], line[t[p].id], t[p].l)){
            t[p].id = v;
        }
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    bool fl = check(line[v], line[t[p].id], t[p].l);
    bool fr = check(line[v], line[t[p].id], t[p].r);
    if (fl && fr){
        t[p].id = v;
        return;
    }
    if (!fl && !fr){
        return;
    }
    if (check(line[v], line[t[p].id], mid)){
        int tmp = t[p].id;
        t[p].id = v;
        if (!fl){
            if (t[p].ls == 0) t[p].ls = newnode(0, 0, 0, t[p].l, mid);
            modify(t[p].ls, tmp);
        }
        else{
            if (t[p].rs == 0) t[p].rs = newnode(0, 0, 0, mid + 1, t[p].r);
            modify(t[p].rs, tmp);
        }
    }
    else{
        if (fl){
            if (t[p].ls == 0) t[p].ls = newnode(0, 0, 0, t[p].l, mid);
            modify(t[p].ls, v);
        }
        else{
            if (t[p].rs == 0) t[p].rs = newnode(0, 0, 0, mid + 1, t[p].r);
            modify(t[p].rs, v);
        }
    }
}
void query(int p, int x, ll &minn){
    if (t[p].id == 0) return;
    minn = min(minn, 1ll * x * line[t[p].id].k + line[t[p].id].b);
    if (t[p].l == t[p].r){
        return;
    }
    int mid = t[p].l + t[p].r >> 1;
    if (x <= mid){
        if (t[p].ls > 0){
            query(t[p].ls, x, minn);
        }
    }
    else{
        if (t[p].rs > 0){
            query(t[p].rs, x, minn);
        }
    }
}
int rt[4 * NR];
void change(int p, int l, int r, int x, int v){
    if (rt[p] == 0) rt[p] = newnode(0, 0, 0, 0, T);
    modify(rt[p], v);
    if (l == r){
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) change(ls(p), l, mid, x, v);
    else change(rs(p), mid + 1, r, x, v);
}
void ask(int p, int l, int r, int L, int R, int x, ll &minn){
    if (rt[p] == 0) return;
    if (L <= l && r <= R){
        query(rt[p], x, minn);
        return;
    }
    int mid = l + r >> 1;
    if (L <= mid) ask(ls(p), l, mid, L, R, x, minn);
    if (R > mid) ask(rs(p), mid + 1, r, L, R, x, minn);
}
int wst(int x, ll y){
    repr(j, 18, 0){
        if (g[x][j] > 0 && h[x][j] <= y){
            x = g[x][j];
            y -= h[x][j];
        }
    }
    return x;
}
void dfs(int u){
    if (u == 1){
        f[u] = 0;
    }
    else{
        f[u] = INF;
        int tmp = wst(u, c[u].l);
        ask(1, 1, n, c[u].pos, c[tmp].pos, c[u].p, f[u]);
        f[u] += c[u].dep * c[u].p + c[u].q;
    }
    line[++tot] = (Line){-c[u].dep, f[u]};
    change(1, 1, n, c[u].pos, tot);
    for (auto kv : e[u]){
        int v = kv.first;
        if (v != c[u].fa){
            dfs(v);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> lyymcl;
    rep(i, 2, n){
        ll w;
        cin >> c[i].fa >> w >> c[i].p >> c[i].q >> c[i].l;
        e[c[i].fa].push_back(make_pair(i, w));
    }
    dfs0(1, 0, 0);
    dfs(1);
    rep(i, 2, n){
        cout << f[i] << endl;
    }
    return 0;
}