NOI2014购票

题意:

给出根节点为 \(1\) 的一颗树，\(d_i\) 表示 \(1\) 到 \(i\) 的距离， 每个点 \(i\) 可以跳到距离 \(\leq l_i\) 的点 \(j\) 上，花费是 \((d_i - d_j) \times p_i + q_i\)，求每个点到根节点的最小花费。

dp 方程转移：

\[f_i = \min \{f_j + (d_i - d_j) \times p_i + q_i\} \]

斜率优化 —— dp 优化

将各项分离，就是可以斜率优化的式子：

\[f_i = \min \{f_j - d_j \times p_i \} + d_i \times p_i + q_i \]

形式化一下:

\[\left \{ \begin{aligned} Y &= f_j \\ X &= d_j \\ K &= p_i \\ D &= d_i \times p_i + q_i \end{aligned} \right. \]

求最小截距 \(B = Y_j - X_j \times K_i + D_i\)。

但是建立可转移点的凸包并不简单，如果插入的 \((X, Y)\) 不保证 \(X\) 的单调性，那么就要用平衡树维护凸包，代码难度爆炸。

点分治 —— 处理树上路径问题

• 在一条链上的 \(d_i\) 是单调的。

利用点分治，对于每个重心，优先处理重心到根节点的子树，先算出它们的 \(f\) 值。

这时再把重心剩下子树的所有节点按照 能到达的深度 大到小排序，依次对于每个结点更新 \(f\) 值，这时分治重心到根的点会依次加入凸包，由于 \(d_i\) 单调递减，
维护一个下凸壳，它的斜率是单调递减的, 可用单调栈维护。

对于每个结点最优决策点，单调栈中的点是它所能到达的所有祖先结点 ，直接用 \(K_i\) 在单调栈二分即可。

代码

#include
using namespace std;

using ll = long long;
const int MAXN = 200010;
const ll INF = 1e18; // 大点
const int mod = 1000000007;

//#define ll long long
template 
void Read(T &x) {
   x = 0; T f = 1; char a = getchar();
   for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
   for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
   x *= f;
}

int n, t;  
int fa[MAXN]; 
ll q[MAXN], p[MAXN], l[MAXN], dis[MAXN], w[MAXN]; 
vector e[MAXN]; 

void getdis(int u) {
   for (int v : e[u]) {
   	dis[v] = dis[u] + w[v];
   	getdis(v); 
   }
}

ll ma, S, root; 
ll siz[MAXN], mx[MAXN]; 
bool vis[MAXN]; 

void getroot(int u) {
   siz[u] = 1;
   mx[u] = 0; 
   for (int v : e[u]) {
   	if (vis[v]) continue;
   	getroot(v);
   	siz[u] += siz[v];
   	mx[u] = max(mx[u], siz[v]); 
   }
   mx[u] = max(mx[u], S - siz[u]); 
   if (mx[u] <= ma) ma = mx[u], root = u; // 只有两个点时，如果找到的重心是 vis 被标 1 的点, 那么它的 siz 就是错的，就会死循环。
}

int len; 
int id[MAXN];
void dfs(int u) {
   id[++ len] = u; 
   for (int v : e[u]) {
   	if (!vis[v])
   		dfs(v); 
   }
}

/*
f[i] = f[j] + (d[i] - d[j]) * p[i] + q[i]
f[i] = f[j] + d[i]p[i] - d[j]*p[i] + q[i] 
Y = f[j]
X = d[j]
K = p[i]
D = q[i] + d[i]p[i]
*/

ll f[MAXN]; 
ll K(int i) {
   return p[i]; 
}
ll X(int j) {
   return dis[j]; 
} 
ll Y(int j) {
   return f[j];
}
ll D(int i) {
   return q[i] + dis[i] * p[i]; 
}
double slope(int i, int j) {
   return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j)); 
}
int top, s[MAXN];
void insert(int x) {
   while(top > 1 && slope(s[top - 1], s[top]) <= slope(s[top], x)) top --;
   s[++ top] = x; 
} 
ll query(int u) {
   int l = 0, r = top; 
   while (l + 1 < r) {
   	int mid = (l + r) >> 1;
   	if (slope(s[mid], s[mid + 1]) <= K(u)) r = mid;
   	else l = mid;
   }
   return s[r]; 
}

void solve(int u, int Siz) { 
   if (Siz == 1) return ;
    
   S = Siz, ma = INF, root = - 1;
   getroot(u); 

   int rt = root; 
   for (int v : e[rt]) {
   	Siz -= siz[v];  
   	vis[v] = 1; 
   }
   solve(u, Siz);
   
   len = 0; 
   for (int v : e[rt])
   	dfs(v); 
   
   sort(id + 1, id + len + 1, [=](int x, int y) {
   	return dis[x] - l[x] > dis[y] - l[y]; 
   });
   int now = rt; top = 0;

   for (int j = 1; j <= len; j ++) {
   	int i = id[j]; 
   	
   	while(now != fa[u] && dis[now] >= dis[i] - l[i]) insert(now), now = fa[now]; 
   	if (top) {
   		int t = query(i); 
   		f[i] = min(f[i], Y(t) - K(i) * X(t) + D(i)); 
   	}
   }
   for (int v : e[rt]) 
   	solve(v, siz[v]); 
}

int main() { 
   Read(n); Read(t);
   for (int i = 2; i <= n; i ++) {
   	Read(fa[i]), Read(w[i]), Read(p[i]), Read(q[i]), Read(l[i]);
   	e[fa[i]].emplace_back(i);  
   	f[i] = INF; 
   }
   getdis(1);
   solve(1, n); 
   for (int i = 2; i <= n; i ++) 
   	printf("%lld\n", f[i]); 

	return 0;
}