由于一棵子树会影响另一棵子树的下凸壳，所以暴力弹出加入是 $O(n^2)$ 的复杂度，而计算答案二分是 $O(n \log n)$ 的。
然后发现实际上由于下凸壳的斜率具有单调性，可以二分出弹出到哪里，然后加入一个新元素 $u$ 只会覆盖原来的一个元素，只需要维护这个东西最后再复原即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15, M = N << 1;
int n, p[N], q[N];
int h[N], e[M], w[M], ne[M], idx = 0;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

long long dp[N], dep[N];

long long x(int p) { return dep[p]; }
long long y(int p) { return dp[p]; }
double slope(int a, int b) {
    if (x(a) == x(b)) {
        if (y(a) < y(b)) return 1e18;
        return -1e18;
    }
    return (y(a) - y(b)) * 1.00 / (x(a) - x(b));
}

int stk[N], top;
void dfs(int u) {
    int id = 0, pre_top = 0;
    if (u != 1) {
        int l = 1, r = top;
        while (l < r) {
            int mid = l + r >> 1;
            if (slope(stk[mid], stk[mid + 1]) <= p[u]) l = mid + 1;
            else r = mid;
        }
        int v = stk[l];
        dp[u] = dp[v] + p[u] * 1ll * (dep[u] - dep[v]) + q[u];
        l = 1, r = top;
        while (l < r) {
            int mid = l + r >> 1;
            if (slope(stk[mid], stk[mid + 1]) < slope(stk[mid + 1], u)) l = mid + 1;
            else r = mid;
        }
        id = stk[l + 1], pre_top = top;
        stk[l + 1] = u, top = l + 1;
    }

    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        dep[v] = dep[u] + w[i];
        dfs(v);
    }

    if (u > 1) stk[top] = id, top = pre_top;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 2, fa, c; i <= n; i++) {
        scanf("%d%d%d%d", &fa, &c, &p[i], &q[i]);
        add(fa, i, c);
    }
    stk[++top] = 1;
    dfs(1);
    for (int i = 2; i <= n; i++) printf("%lld\n", dp[i]);
    return 0;
}