首先易得方程，且经过变换有
$$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}$$
在一条直线上时，斜率优化可以用普通$CDQ$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治
这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了
注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包
代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 7 using namespace std; 8 9 typedef long long LL; 10 11 const int MAXN = 2e05 + 10; 12 const int MAXM = 2e05 + 10; 13 14 const int INF = 0x7fffffff; 15 const LL INFLL = 0x3f3f3f3f3f3f3f3f; 16 const double eps = 1e-08; 17 18 int Dcmp (double p) { 19 if (fabs (p) < eps) 20 return 0; 21 return p < 0 ? - 1 : 1; 22 } 23 24 struct LinkedForwardStar { 25 int to; 26 27 int next; 28 } ; 29 30 LinkedForwardStar Link[MAXM << 1]; 31 int Head[MAXN]= {0}; 32 int size = 0; 33 34 void Insert (int u, int v) { 35 Link[++ size].to = v; 36 Link[size].next = Head[u]; 37 38 Head[u] = size; 39 } 40 41 const int Root = 1; 42 43 struct CitySt { 44 LL p, q, lim; 45 46 CitySt () {} 47 } ; 48 CitySt City[MAXN]; 49 50 LL f[MAXN]; 51 52 int N; 53 LL Fdist[MAXN]= {0}; 54 55 LL Dist[MAXN]= {0}; 56 int Father[MAXN]= {0}; 57 void DFS (int root, int father) { 58 for (int i = Head[root]; i; i = Link[i].next) { 59 int v = Link[i].to; 60 if (v == father) 61 continue; 62 Dist[v] = Dist[root] + Fdist[v]; 63 DFS (v, root); 64 } 65 } 66 67 int Vis[MAXN]= {0}; 68 69 int Size[MAXN]= {0}; 70 int grvy, minval = INF; 71 int total; 72 void Grvy_Acqu (int root, int father) { 73 Size[root] = 1; 74 int maxpart = 0; 75 for (int i = Head[root]; i; i = Link[i].next) { 76 int v = Link[i].to; 77 if (v == father || Vis[v]) 78 continue; 79 Grvy_Acqu (v, root); 80 Size[root] += Size[v]; 81 maxpart = max (maxpart, Size[v]); 82 } 83 maxpart = max (maxpart, total - Size[root]); 84 if (maxpart < minval) 85 grvy = root, minval = maxpart; 86 } 87 88 int temp[MAXN]; 89 int p = 0; 90 int Que[MAXN]; 91 double slope (int a, int b) { 92 if (Dist[a] == Dist[b]) 93 return INFLL * 1.0; 94 return (double) (f[b] - f[a]) * 1.0 / (double) (Dist[b] - Dist[a]) * 1.0; 95 } 96 int listq[MAXN]; 97 int lp = 0; 98 bool comp (const int& a, const int& b) { 99 return Dist[a] - City[a].lim > Dist[b] - City[b].lim; 100 } 101 void listq_Acqu (int root, int father) { 102 if (father) 103 listq[++ lp] = root; 104 for (int i = Head[root]; i; i = Link[i].next) { 105 int v = Link[i].to; 106 if (v == father || Vis[v]) 107 continue; 108 listq_Acqu (v, root); 109 } 110 } 111 int Binary_Search (int left, int right, int p) { 112 if (left == right) 113 return left; 114 int l = left, r = right; 115 while (l < r) { 116 int mid = (l + r) >> 1; 117 if (f[Que[mid + 1]] - f[Que[mid]] <= p * (Dist[Que[mid + 1]] - Dist[Que[mid]])) 118 l = mid + 1; 119 else 120 r = mid; 121 } 122 return l; 123 } 124 void Update (int left, int right, int tp) { 125 if (left > right) 126 return ; 127 int p = Binary_Search (left, right, City[tp].p); 128 f[tp] = min (f[tp], f[Que[p]] + (Dist[tp] - Dist[Que[p]]) * City[tp].p + City[tp].q); 129 } 130 void Solve (int root) { 131 minval = INF, total = Size[root], Grvy_Acqu (root, 0); 132 Vis[grvy] = true; 133 int fgrvy = grvy; 134 if (grvy != root) { 135 Size[root] -= Size[grvy]; 136 Solve (root); 137 } 138 p = 0; 139 temp[++ p] = fgrvy; 140 for (int nd = fgrvy; nd != root; nd = Father[nd]) { 141 if (Dist[fgrvy] - City[fgrvy].lim <= Dist[Father[nd]]) 142 f[fgrvy] = min (f[fgrvy], f[Father[nd]] + (Dist[fgrvy] - Dist[Father[nd]]) * City[fgrvy].p + City[fgrvy].q); 143 temp[++ p] = Father[nd]; 144 } 145 lp = 0; 146 listq_Acqu (fgrvy, 0); 147 sort (listq + 1, listq + lp + 1, comp); 148 int left = 1, right = 0; 149 int j = 1; 150 for (int i = 1; i <= p && j <= lp; i ++) { // 斜率优化 151 while (j <= lp && Dist[temp[i]] < Dist[listq[j]] - City[listq[j]].lim) 152 Update (left, right, listq[j ++]); 153 while (left < right && Dcmp (slope (Que[right - 1], Que[right]) - slope (Que[right], temp[i])) <= 0) // 注意是上凸包 154 right --; 155 Que[++ right] = temp[i]; 156 } 157 while (j <= lp) 158 Update (left, right, listq[j ++]); 159 for (int i = Head[fgrvy]; i; i = Link[i].next) { 160 int v = Link[i].to; 161 if (Vis[v]) 162 continue; 163 Solve (v); 164 } 165 } 166 167 int getint () { 168 int num = 0; 169 char ch = getchar (); 170 171 while (! isdigit (ch)) 172 ch = getchar (); 173 while (isdigit (ch)) 174 num = (num << 3) + (num << 1) + ch - '0', ch = getchar (); 175 176 return num; 177 } 178 179 LL getLL () { 180 LL num = 0; 181 char ch = getchar (); 182 183 while (! isdigit (ch)) 184 ch = getchar (); 185 while (isdigit (ch)) 186 num = (num << 3) + (num << 1) + ch - '0', ch = getchar (); 187 188 return num; 189 } 190 191 int main () { 192 // freopen ("Input.txt", "r", stdin); 193 // freopen ("Output.txt", "w", stdout); 194 195 memset (f, 0x3f3f3f3f, sizeof (f)); 196 f[Root] = 0; 197 N = getint (), getint (); 198 for (int i = 2; i <= N; i ++) { 199 int fa = getint (); 200 Father[i] = fa; 201 Fdist[i] = getLL (); 202 City[i].p = getLL (), City[i].q = getLL (), City[i].lim = getLL (); 203 Insert (fa, i), Insert (i, fa); 204 } 205 DFS (Root, 0); 206 Size[Root] = N; 207 Solve (Root); 208 for (int i = 2; i <= N; i ++) 209 printf ("%lld\n", f[i]); 210 211 return 0; 212 } 213 214 /* 215 7 3 216 1 2 20 0 3 217 1 5 10 100 5 218 2 4 10 10 10 219 2 9 1 100 10 220 3 5 20 100 10 221 4 4 20 0 10 222 */