Problem: log_drivin_hirin (2020 round2)

The rapid flow of rivers is an effective way to move logs in the great Canadian log drive. But as every Canadian knows, it can be a double-edged sword. If logs get stuck on the riverbanks, they'll eventually pile up and cause the river to overflow. [Sometimes you need a helping hand to keep the logs moving](https://youtu.be/7AheBqBk0iQ?t=578).

In a given river system there are \(N\) lakes, numbered from \(1\) to \(N\), and \(N-1\) rivers flowing amongst the lakes. For each lake \(i\) such that \(2 \le i \le N\), there's a river flowing from lake \(P_i\) to lake \(i\) which is \(L_i\) metres long. There are no rivers flowing into lake 1. \(P_1\) and \(L_1\) are defined to be equal to 0, but are irrelevant. It's guaranteed that each lake is accessible from lake 1 by some sequence of rivers. Each lake with no rivers flowing out of it has a log-processing plant.

Shipments of logs are often transported through these lakes and rivers. Each shipment consists of some number of logs, and is managed by a log driver with some integer carelessness value. A shipment may be transported from a lake by means of a river flowing out of it, to the lake which that river flows into. However, a number of logs will be permanently lost along the way, equal to the log driver's carelessness value multiplied by the length of the river (in metres). We can assume that shipments are always large enough that they don't risk completely running out of logs. Each shipment continues to be transported from lake to lake until reaching a log-processing plant.

Other log drivers available for hire also live by the lakes. There's a log driver living by each lake \(i\) with a carelessness of \(H_i\). Whenever a shipment of logs is at lake \(i\), the company that owns the shipment may choose to hire the log driver there to take over in place of the shipment's current log driver. The newly-hired log driver will then manage the shipment until it either reaches a log-processing plant, or another log driver is later hired to replace them.

As part of the log-istics team, you need to answer \(M\) questions, the \(i\)th of which asks: If you begin with a shipment of logs in lake \(X_i\), being managed by a log driver with a carelessness of \(Y_i\), what's the minimum number of logs which can be lost by the time the shipment reaches any log-processing plant? Please note that each question is independent of the others (for example, the same log driver may be hired as part of the answer to multiple different questions).

Let \(V_i\) be the answer to the \(i\)th question. In order to reduce the size of the output, you must calculate a single integer: the product of \((V_i + 1)\) over \(i=1..M\). As this product may be very large, you should only compute its value modulo 1,000,000,007.

In order to reduce the size of the input, the above values will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(P_{1..K}\), \(L_{1..K}\), \(H_{1..K}\), \(X_{1..K}\), and \(Y_{1..K}\), as well as the five tuples of constants \((A_P, B_P, C_P)\), \((A_L, B_L, C_L, D_L)\), \((A_H, B_H, C_H, D_H)\), and \((A_X, B_X, C_X)\), \((A_Y, B_Y, C_Y, D_Y)\), and must then compute \(P_{(K+1)..N}\), \(L_{(K+1)..N}\), \(H_{(K+1)..N}\), \(X_{(K+1)..M}\), and \(Y_{(K+1)..M}\) as follows:

\(P_i = ((A_P * P_{i-2} + B_P * P_{i-1} + C_P) \text{ modulo } (i-1)) + 1\)  for \(i > K\)
\(L_i = ((A_L * L_{i-2} + B_L * L_{i-1} + C_L) \text{ modulo } D_L) + 1\)  for \(i > K\)
\(H_i = ((A_H * H_{i-2} + B_H * H_{i-1} + C_H) \text{ modulo } D_H) + 1\)  for \(i > K\)
\(X_i = ((A_X * X_{i-2} + B_X * X_{i-1} + C_X) \text{ modulo } N) + 1\) for \(i > K\)
\(Y_i = ((A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y) \text{ modulo } D_Y) + 1\)  for \(i > K\)

# Constraints

\(1 \le T \le 85\)
\(2 \le N, M \le 1,000,000\)
\(2 \le K \le min(N, M)\)
\(0 \le A_P, B_P, C_P, A_L, B_L, C_L, A_H, B_H, C_H, A_X, B_X, C_X, A_Y, B_Y, C_Y <= 1,000,000,000\)
\(1 \le D_L, D_H, D_Y \le 1,000,000\)
\(0 \le P_i \le i-1\)  (\(P_i = 0\) if and only if \(i = 1\))
\(0 \le L_i \le D_L\)  (\(L_i = 0\) if and only if \(i = 1\))
\(1 \le H_i \le D_H\)
\(1 \le X_i \le N\)
\(1 \le Y_i \le D_Y\)

The sum of \(N+M\) over all \(T\) test cases is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of river systems. For each system, there are 11 lines:

The first line contains the 3 space-separated integers \(N\), \(M\), and \(K\).

The second line contains the \(K\) space-separated integers \(P_{1..K}\).

The third line contains the 3 space-separated integers \(A_P\), \(B_P\), and \(C_P\).

The fourth line contains the \(K\) space-separated integers \(L_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_L\), \(B_L\), \(C_L\), and \(D_L\).

The sixth line contains the \(K\) space-separated integers \(H_{1..K}\).

The seventh line contains the 4 space-separated integers \(A_H\), \(B_H\), \(C_H\), and \(D_H\).

The eighth line contains the \(K\) space-separated integers \(X_{1..K}\).

The ninth line contains the 3 space-separated integers \(A_X\), \(B_X\), and \(C_X\).

The tenth line contains the \(K\) space-separated integers \(Y_{1..K}\).

The eleventh line contains the 4 space-separated integers \(A_Y\), \(B_Y\), \(C_Y\), and \(D_Y\).

# Output

For the \(i\)th river system, print a line containing *"Case #i: "* followed by a single integer, the product of \((V_i + 1)\) over \(i=1..M\), modulo 1,000,000,007.

# Explanation of Sample

**In the first case:**

- \(P = [0, 1, 2]\)
- \(L = [0, 2, 3]\)
- \(H = [10, 5, 50]\)
- \(X = [1, 1, 2, 3]\)
- \(Y = [2, 8, 3, 1]\)

The system of lakes and rivers looks as follows (with hireable log drivers' carelessness values indicated in circles, and lakes with log-processing plants marked in brown):

{{PHOTO_ID:896677524192910}}

- The first question deals with a shipment of logs at lake \(1\) being managed by a log driver with carelessness \(2\). It's optimal for this log driver to move the shipment to lake \(2\) (while losing \(2 * 2 = 4\) logs), and then to lake \(3\) (losing another \(3 * 2 = 6\) logs), with a total of \(10\) logs lost.
- For the second question, the log driver should move the shipment to lake \(2\) and then be replaced by the log driver living there (who has a carelessness of \(5\)), who will move it to lake \(3\). This would result in a total of \(2 * 8 + 3 * 5 = 31\) logs lost.
- For the third question, the log driver should move the shipment to lake \(3\), losing \(3 * 3 = 9\) logs along the way.
- For the fourth question, the shipment begins at a lake with a log-processing plant, meaning that no logs need to be lost.
  
Therefore, \(V = [10, 31, 9, 0]\), and the final answer is \(((10 + 1) * (31 + 1) * (9 + 1) * (0 + 1))\text{ modulo 1,000,000,007} = 3520\).

**In the second case:**

- \(P = [0, 1, 2, 1, 2, 4]\)
- \(L = [0, 11, 12, 13, 14, 15]\)
- \(H = [5, 4, 7, 2, 1, 3]\)
- \(X = [1, 2, 4, 1, 2, 1]\)
- \(Y = [1, 2, 3, 4, 5, 6]\)

The system of lakes and rivers looks as follows:

{{PHOTO_ID:3296189243803342}}

For the first question, the log driver should move the shipment to lake \(2\) and then to lake \(3\), losing a total of \(11 * 1 + 12 * 1 = 23\) logs along the way. Overall, \(V = [23, 24, 30, 82, 48, 95]\).

**In the third case:**

- \(P = [0, 1, 2, 2, 2, 1, 6, 5]\)
- \(L = [0, 5, 1, 8, 3, 2, 9, 8]\)
- \(H = [10, 9, 8, 7, 6, 5, 4, 3]\)
- \(X = [5, 1, 2, 1, 8, 5, 4, 1, 8, 5]\)
- \(Y = [6, 2, 9, 8, 9, 4, 9, 4, 9, 4]\)

For this case, \(V = [48, 12, 9, 48, 0, 32, 0, 24, 0, 32]\).


Sample input:
4
3 4 3
0 1 2
0 0 0
0 2 3
0 0 0 100
10 5 50
0 0 0 100
1 1 2
0 0 2
2 8 3
0 0 100 100
6 6 6
0 1 2 1 2 4
0 0 0
0 11 12 13 14 15
0 0 0 100
5 4 7 2 1 3
0 0 0 100
1 2 4 1 2 1
0 0 0
1 2 3 4 5 6
0 0 0 100
8 10 4
0 1 2 2
4 8 1
0 5 1 8
2 3 6 10
10 9 8 7
0 1 8 10
5 1 2 1
4 7 8
6 2 9 8
5 0 3 10
15 30 2
0 1
4 5 6
0 33
1 2 3 123
45 193
11 22 33 321
12 3
111 222 333
402 172
1111 2222 3333 531


Sample output:
Case #1: 3520
Case #2: 262035151
Case #3: 497739194
Case #4: 762796014


Solution: The lakes and rivers may be represented as a tree rooted at node (lake) \(1\). Let \(D_i\) be the total distance along rivers from the root to each node \(i\).

Let \(Q(i, c)\) be the minimum number of logs which may be lost for a shipment of logs which begins at node \(i\) while being managed by a log driver with a carelessness of \(c\) (such that \(V_i = Q(X_i, Y_i)\)).

If node \(i\) has a log-processing plant (i.e. is a leaf node), \(Q(i, c) = 0\) for any \(c\). Otherwise, \(Q(i, c)\) may be computed by considering possible options for the first "relevant node" \(j\) encountered by a shipment beginning at node \(i\), such that either \(j\) is a leaf node or the first node at which a new log driver will be hired (note that \(j\) must be within \(i\)'s subtree, and may be equal to \(i\) itself). For a given choice of \(j\), the number of logs lost for the shipment comes out to \(c(D_j - D_i) + Q(j, H_j)\), and so we're looking for the node \(j\) which minimizes this expression.

Rewriting the expression as \(cD_j + Q(j, H_j) - cD_i\), and ignoring the final portion (which is independent of \(j\)), we can observe that it forms a linear equation \(F_j(c) = m_j c + b_j\) (where \(m_j = D_j\) and \(b_j = Q(j, H_j)\)). As such, we've reduced computing \(Q(i, c)\) to finding the minimum value of \(F_j(c)\) over all nodes \(j\) in \(i\)'s subtree. To avoid an infinitely recursive definition, note that we can evaluate \(Q(i, H_i)\) by only considering nodes \(j\) such that \(j \ne i\).

Our approach will involve recursively traversing the tree, such that for each node \(i\), we compute \(Q(i, H_i)\) followed by \(Q(X_k, Y_k)\) for each question such that \(X_k = i\). Along the way, we'll need to maintain information around the linear equations \(F_j(c)\) for all nodes \(j\) in \(i\)'s subtree, so that we can efficiently compute each \(Q(i, c)\) value.

Making use of the *dynamic convex hull trick*, we'll store these linear equations in a set ordered by their slope (\(m_y\)), such that each equation yields the minimum result out of all equations when evaluated for some non-empty interval of \(c\) values. Our data structure will also store the "intersection points" of all consecutive pairs of linear equations in the ordered set, which correspond to the intervals of \(c\) values for which the various equations are optimal. With this setup, we're able to insert a new equation into the set and to query the minimum value of any equation for a given value of \(c\) in \(O(log(n))\) time each (where \(n\) is the number of equations in the set).

The remaining question is how we'll build up these sets of equations for entire subtrees of nodes. When handling each node \(i\), we must efficiently merge all of its children's sets together, before proceeding to compute and insert \(F_i\) as well. When merging two sets together, we should simply elect to reuse the larger of the two (or an arbitrary one if they have the same size), inserting all equations from the smaller one into it and then discarding that smaller set. Each time a given equation is merged into a different set, the size of its containing set at least doubles, meaning that it may be inserted into sets at most \(O(log(N))\) times. With each set consisting of up to \(N\) equations, the total time complexity of all insertions comes out to \(O(N log^2(N))\). Factoring in the set queries required to evaluate all \(N + M\) needed \(Q(i, c)\) values, we arrive at a total of \(O(N log^2(N) + M log(N))\) time.



Code: // Log Drivin' Hirin'
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x) {
  char c, r = 0, n = 0;
  x = 0;
  for (;;) {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      x = x * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n)
    x = -x;
  return(1);
}

struct Line {
  mutable LL k, m, p;
  bool operator<(const Line& o) const { return k < o.k; }
  bool operator<(LL x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
  const LL inf = LLONG_MAX;
  LL div(LL a, LL b) { // floored division
    return a / b - ((a ^ b) < 0 && a % b);
  }
  bool isect(iterator x, iterator y) {
    if (y == end()) { x->p = inf; return false; }
    if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    else x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(LL k, LL m) {
    auto z = insert({ k, m, 0 }), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p)
      isect(x, erase(y));
  }
  LL query(LL x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return l.k * x + l.m;
  }
};

#define LIM 1000001
#define MOD 1000000007

int N, M, K, ans;
int P[LIM], L[LIM], H[LIM], X[LIM], Y[LIM];
vector<int> ch[LIM], Q[LIM];
int nid, id[LIM];
LineContainer LC[LIM];

void ReadSeq(int* V, int N, int K, int mod)
{
  int i, A, B, C;
  Fox(i, K)
    Read(V[i]);
  Read(A), Read(B), Read(C);
  if (!mod)
    Read(mod);
  FoxI(i, K, N - 1)
    V[i] = ((LL)A * V[i - 2] + (LL)B * V[i - 1] + C) % (mod < 0 ? i : mod) + 1;
}

LL GetQueryAns(int i, LL d, int c)
{
  return(c * d + LC[id[i]].query(c));
}

void rec(int i, LL d)
{
  // init new line container
  id[i] = nid++;
  // recurse to children
  for (auto c : ch[i])
  {
    rec(c, d + L[c]);
    // merge smaller line container into larger one
    int& a = id[i], & b = id[c];
    if (Sz(LC[a]) < Sz(LC[b]))
      swap(a, b);
    for (auto ln : LC[b])
      LC[a].add(ln.k, ln.m);
    LC[b].clear();
  }
  // add line for hireable log driver or leaf node
  LC[id[i]].add(-d, Sz(ch[i]) ? GetQueryAns(i, d, H[i]) : 0);
  // answer queries at this node
  for (auto c : Q[i])
    ans = ans * ((-GetQueryAns(i, d, c) + 1) % MOD) % MOD;
  ch[i].clear(), Q[i].clear();
}

int ProcessCase()
{
  int i;
  // input
  Read(N), Read(M), Read(K);
  ReadSeq(P, N, K, -1);
  ReadSeq(L, N, K, 0);
  ReadSeq(H, N, K, 0);
  ReadSeq(X, M, K, N);
  ReadSeq(Y, M, K, 0);
  // init tree/queries
  Fox1(i, N - 1)
    ch[P[i] - 1].pb(i);
  Fox(i, M)
    Q[X[i] - 1].pb(Y[i]);
  // compute answers
  ans = 1;
  nid = 0;
  rec(0, 0);
  LC[id[0]].clear();
  return(ans);
}

int main() {
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}