題意 "題目鏈接" Sol 介紹一種神奇的點分治的做法 啥？這都有根樹了怎麼點分治？？ 嘿嘿，這道題的點分治不同於一般的點分治。正常的點分治思路大概是先統計過重心的，再遞歸下去 實際上一般的點分治與統計順序關係不大，也就是說我可以先統計再遞歸，或者先遞歸再統計。 但是這題不單單是統計，它是dp，存在 ...
題意
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
*/
