题意

题目链接

Sol

介绍一种神奇的点分治的做法

啥？这都有根树了怎么点分治？？

嘿嘿，这道题的点分治不同于一般的点分治。正常的点分治思路大概是先统计过重心的，再递归下去

实际上一般的点分治与统计顺序关系不大，也就是说我可以先统计再递归，或者先递归再统计。

但是这题不单单是统计，它是dp，存在决策顺序问题，我们就需要换一种思路了。

首先我们可以这样考虑：对于每个点\(x\)，找出子树重心\(root\)，对除去重心外的部分递归执行该操作，那么回溯回来的时候，我们默认除重心的子树外答案都已经更新好了。

接下来考虑重心子树内的点的转移，我们只需要考虑从\(root\)到\(x\)的路径，显然排序之后双指针可以做到\(nlogn\)的复杂度。(对转移位置按深度排序，对要更新的点按深度 - 限制长度排序，双指针的时候维护一下凸包，因为\(p\)不单调所以需要在凸包上二分)

复杂度不太会严格的证明，但是跑的飞快。因为虽然我们的分治结构变了，但每次还是找重心更新答案，所以复杂度是有保证的。

#include<bits/stdc++.h>

#define int long long

#define LL long long

using namespace std;

const int MAXN = 1e6 + 10, mod = 1e9 + 7, INF = 3e18 + 10;

const double eps = 1e-9;

template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}

template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}

template <typename A> inline void debug(A a){cout << a << '\n';}

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, T, fa[MAXN], d[MAXN], pp[MAXN], qq[MAXN], lim[MAXN], siz[MAXN], Sum, vis[MAXN], Mx, root, f[MAXN], st[MAXN], top, cnt;

vector<int> v[MAXN];

void dfs(int x) {

    d[x] += d[fa[x]]; siz[x] = 1;

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa[x]) continue;

        dfs(to); siz[x] += siz[to];

    }

}

void Find(int x) {

    //printf("%d\n", x);

    int mx = 0; siz[x] = 1;

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa[x] || vis[to]) continue;

        Find(to); siz[x] += siz[to];

        chmax(mx, siz[to]);

    }

    chmax(mx, Sum - siz[x]);

    if(mx < Mx && siz[x] > 1) Mx = mx, root = x;

}

struct Node {

    int id, dis;

    bool operator < (const Node &rhs) const {

        return dis > rhs.dis;

    }

}a[MAXN];

void dfs2(int x) {

    a[++cnt].id = x;

    a[cnt] = (Node) {x, d[x] - lim[x]};

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa[x] || vis[to]) continue;

        dfs2(to);

    }

}

int Y(int x) {

    return f[x];

}

int X(int x) {

    return d[x];

}

double slope(int x, int y) {

    return (double) (Y(y) - Y(x)) / (X(y) - X(x));

}

void insert(int x) {

    while(top > 1 && slope(st[top], x) > slope(st[top - 1], st[top])) top--;

    st[++top] = x;

}

int Search(double x, int id) {

    if(!top) return INF;

    int l = 1, r = top - 1, ans = 1;

    while(l <= r) {

        int mid = l + r >> 1;

        if((slope(st[mid], st[mid + 1]) >= x)) ans = mid + 1, l = mid + 1;

        else r = mid - 1;

    }

    return f[st[ans]] - d[st[ans]] * pp[id];

}

void solve(int x, int tot, int up) {

    vector<int> pot;

    for(int t = x; t != up; t = fa[t])

        pot.push_back(t);

    cnt = 0;

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa[x]) continue;

        dfs2(to);//dep´Ó´óµ½´ïС£¬dis´Ó´óµ½Ð¡

    }

    sort(a + 1, a + cnt + 1);

    int now = 0; top = 0;

    for(int i = 1; i <= cnt; i++) {

        int cur = a[i].id;

        while(now <= pot.size() - 1 && d[pot[now]] >= a[i].dis) insert(pot[now++]);

        chmin(f[cur], Search(pp[cur], cur) + qq[cur] + d[cur] * pp[cur]);

    }

}

void work(int x, int tot) {

    if(tot == 1) return ;

    root = x; Sum = tot; Mx = Sum; Find(root);

    int rt = root;

    for(int i = 0; i < v[rt].size(); i++) {

        int to = v[rt][i]; if(to == fa[rt]) continue;

        vis[to] = 1;

    }

    work(x, tot - siz[root] + 1);

    solve(rt, tot, fa[x]);

    for(int i = 0; i < v[rt].size(); i++) {

        int to = v[rt][i]; if(to == fa[rt]) continue;

        work(to, siz[to]);

    }

}

signed main() {

    //freopen("a.in", "r", stdin);

    N = read(); T = read();

    for(int i = 2; i <= N; i++) {

        fa[i] = read();

        v[fa[i]].push_back(i); v[i].push_back(fa[i]);

        d[i] = read(); pp[i] = read(); qq[i] = read();  lim[i] = read();

    }

    dfs(1);

    memset(f, 0x7f7f7f, sizeof(f)); f[1] = 0;

    work(1, N);

    for(int i = 2; i <= N; i++) cout << f[i] << '\n';

    return 0;

}

/*

7 3

1 2 20 0 3

1 5 10 100 5

2 4 10 10 10

2 9 1 100 10

3 5 20 100 10

4 4 20 0 10

*/