[NOI2014]购票 「树上斜率优化」

时间：2023-03-09 15:22:18
[NOI2014]购票 「树上斜率优化」

首先易得方程，且经过变换有

$$\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$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了

注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包

代码

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 typedef long long LL;

 const int MAXN = 2e05 + ;

 const int MAXM = 2e05 + ;

 const int INF = 0x7fffffff;

 const LL INFLL = 0x3f3f3f3f3f3f3f3f;

 const double eps = 1e-;

 int Dcmp (double p) {

     if (fabs (p) < eps)

         return ;

     return p <  ? -  : ;

 }

 struct LinkedForwardStar {

     int to;

     int next;

 } ;

 LinkedForwardStar Link[MAXM << ];

 int Head[MAXN]= {};

 int size = ;

 void Insert (int u, int v) {

     Link[++ size].to = v;

     Link[size].next = Head[u];

     Head[u] = size;

 }

 const int Root = ;

 struct CitySt {

     LL p, q, lim;

     CitySt () {}

 } ;

 CitySt City[MAXN];

 LL f[MAXN];

 int N;

 LL Fdist[MAXN]= {};

 LL Dist[MAXN]= {};

 int Father[MAXN]= {};

 void DFS (int root, int father) {

     for (int i = Head[root]; i; i = Link[i].next) {

         int v = Link[i].to;

         if (v == father)

             continue;

         Dist[v] = Dist[root] + Fdist[v];

         DFS (v, root);

     }

 }

 int Vis[MAXN]= {};

 int Size[MAXN]= {};

 int grvy, minval = INF;

 int total;

 void Grvy_Acqu (int root, int father) {

     Size[root] = ;

     int maxpart = ;

     for (int i = Head[root]; i; i = Link[i].next) {

         int v = Link[i].to;

         if (v == father || Vis[v])

             continue;

         Grvy_Acqu (v, root);

         Size[root] += Size[v];

         maxpart = max (maxpart, Size[v]);

     }

     maxpart = max (maxpart, total - Size[root]);

     if (maxpart < minval)

         grvy = root, minval = maxpart;

 }

 int temp[MAXN];

 int p = ;

 int Que[MAXN];

 double slope (int a, int b) {

     if (Dist[a] == Dist[b])

         return INFLL * 1.0;

     return (double) (f[b] - f[a]) * 1.0 / (double) (Dist[b] - Dist[a]) * 1.0;

 }

 int listq[MAXN];

 int lp = ;

 bool comp (const int& a, const int& b) {

     return Dist[a] - City[a].lim > Dist[b] - City[b].lim;

 }

 void listq_Acqu (int root, int father) {

     if (father)

         listq[++ lp] = root;

     for (int i = Head[root]; i; i = Link[i].next) {

         int v = Link[i].to;

         if (v == father || Vis[v])

             continue;

         listq_Acqu (v, root);

     }

 }

 int Binary_Search (int left, int right, int p) {

     if (left == right)

         return left;

     int l = left, r = right;

     while (l < r) {

         int mid = (l + r) >> ;

         if (f[Que[mid + ]] - f[Que[mid]] <= p * (Dist[Que[mid + ]] - Dist[Que[mid]]))

             l = mid + ;

         else

             r = mid;

     }

     return l;

 }

 void Update (int left, int right, int tp) {

     if (left > right)

         return ;

     int p = Binary_Search (left, right, City[tp].p);

     f[tp] = min (f[tp], f[Que[p]] + (Dist[tp] - Dist[Que[p]]) * City[tp].p + City[tp].q);

 }

 void Solve (int root) {

     minval = INF, total = Size[root], Grvy_Acqu (root, );

     Vis[grvy] = true;

     int fgrvy = grvy;

     if (grvy != root) {

         Size[root] -= Size[grvy];

         Solve (root);

     }

     p = ;

     temp[++ p] = fgrvy;

     for (int nd = fgrvy; nd != root; nd = Father[nd]) {

         if (Dist[fgrvy] - City[fgrvy].lim <= Dist[Father[nd]])

             f[fgrvy] = min (f[fgrvy], f[Father[nd]] + (Dist[fgrvy] - Dist[Father[nd]]) * City[fgrvy].p + City[fgrvy].q);

         temp[++ p] = Father[nd];

     }

     lp = ;

     listq_Acqu (fgrvy, );

     sort (listq + , listq + lp + , comp);

     int left = , right = ;

     int j = ;

     for (int i = ; i <= p && j <= lp; i ++) { // 斜率优化

         while (j <= lp && Dist[temp[i]] < Dist[listq[j]] - City[listq[j]].lim)

             Update (left, right, listq[j ++]);

         while (left < right && Dcmp (slope (Que[right - ], Que[right]) - slope (Que[right], temp[i])) <= ) // 注意是上凸包

             right --;

         Que[++ right] = temp[i];

     }

     while (j <= lp)

         Update (left, right, listq[j ++]);

     for (int i = Head[fgrvy]; i; i = Link[i].next) {

         int v = Link[i].to;

         if (Vis[v])

             continue;

         Solve (v);

     }

 }

 int getint () {

     int num = ;

     char ch = getchar ();

     while (! isdigit (ch))

         ch = getchar ();

     while (isdigit (ch))

         num = (num << ) + (num << ) + ch - '', ch = getchar ();

     return num;

 }

 LL getLL () {

     LL num = ;

     char ch = getchar ();

     while (! isdigit (ch))

         ch = getchar ();

     while (isdigit (ch))

         num = (num << ) + (num << ) + ch - '', ch = getchar ();

     return num;

 }

 int main () {

     // freopen ("Input.txt", "r", stdin);

     // freopen ("Output.txt", "w", stdout);

     memset (f, 0x3f3f3f3f, sizeof (f));

     f[Root] = ;

     N = getint (), getint ();

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

         int fa = getint ();

         Father[i] = fa;

         Fdist[i] = getLL ();

         City[i].p = getLL (), City[i].q = getLL (), City[i].lim = getLL ();

         Insert (fa, i), Insert (i, fa);

     }

     DFS (Root, );

     Size[Root] = N;

     Solve (Root);

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

         printf ("%lld\n", f[i]);

     return ;

 }

 /*

 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

 */

相关文章