Problem: vacation (2021 finals)

Melody is planning her Christmas vacation in the Metalverse, an ore-rich VR experience consisting of \(T\) virtual worlds.

A given world has \(N\) cities (numbered from \(1\) to \(N\)) with \(N - 1\) roads running between them. The \(i\)th road allows Melody to drive between cities \(P_i\) and \(i+1\) in either direction (with \(1 \le P_i \le i\)). City \(i\) also contains \(C_i\) ore-naments which Melody can collect as souvenirs while she's there.

Melody's vacation consists of starting in any city of her choice, and then repeatedly performing either of the following actions:

  1. Drive along a road to another city, unless her previous action was to drive *from* that city
  2. Teleport to any other city

Melody may visit a city multiple times, but may only collect its ore-naments once. She may stop her vacation at any point.

Please help Melody evaluate, for each world, the minimum number of times she must teleport to collect at least K ore-naments, if it's possible at all.

# Constraints

\(1 \le T \le 95\)
\(2 \le N \le 10^6\)
\(1 \le K \le 10^{12}\)
\(0 \le C_i \le 10^9\)
\(1 \le P_i \le i\)

The sum of \(N\) across all worlds is at most \(5{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of virtual worlds to be evaluated. For each world, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, there is a line containing \(N\) space-separated integers, \(C_{1..N}\). Then, there is a line containing \(N-1\) space-separated integers, \(P_{1..(N-1)}\).

# Output

For the \(i\)th world, print a line containing *"Case #i: "* followed a single integer, the minimum number of times Melody must teleport to collect at least \(K\) ore-naments, or \(-1\) if it's impossible to do so.

# Sample Explanation

In the first three worlds, the cities are arranged as follows:

{{PHOTO_ID:2893643357566792|WIDTH:300}}

In the first world, one option is to start in city \(4\), drive to city \(2\), and finally drive to city \(3\). This will yield \(40 + 20 + 30 = 90\) ore-naments.

In the second world, one option is to start in city \(2\), drive to city \(1\), teleport to city \(3\), drive to city \(2\), and finally drive to city \(4\). This will yield \(20 + 10 + 30 + 0 + 40 = 100\) ore-naments.


Sample input:
6
4 90
10 20 30 40
1 2 2
4 91
10 20 30 40
1 2 2
4 101
10 20 30 40
1 2 2
5 222
1 1 100 100 100
1 1 2 2
8 35
3 5 7 2 4 8 1 6
1 2 1 4 4 1 4
8 36
3 5 7 2 4 8 1 6
1 2 1 4 4 1 4


Sample output:
Case #1: 0
Case #2: 1
Case #3: -1
Case #4: 1
Case #5: 1
Case #6: 2


Solution: Note that the network of cities and roads form a tree (which we consider to be rooted at node \(1\)), and that a vacation using \(t\) teleports is equivalent to a set of \(t+1\) simple paths on the tree, with ore-naments collected from all nodes present in at least one path.

We'll begin by considering a different variation of this problem, in which each path used incurs some constant penalty of \(P\) ore-naments (such that, if \(o\) ore-naments are collected using \(p\) paths, the final ore-nament count \(x\) will be \(o - p * P\)). In this variation, let's maximize \(x\), breaking ties by minimizing \(p\).

This variation is solvable using DP, letting \(DP_{i,j}\) be the optimal pair of \((x, p)\) for node \(i\)'s subtree, such that \(j\) paths are ongoing between node \(i\) and its parent (with those \(j\) paths not included in \(x\) and \(p\)). The overall answer will then be \(DP_{1,0}\). We can observe that values of \(j\) up to \(2\) are relevant (as there must be an optimal set of paths such that no tree edge is part of \(3\) or more paths). This means there are only \(O(N)\) states, which are all possible to evaluate in linear time. A key aspect of the implementation is only counting each path and its penalty once, for example only at its topmost node (when it doesn't continue from node \(i\) up to its parent, due to either ending there or feeding into two of \(i\)'s children).

To now solve the original problem, we can employ a technique which goes by various names, including "parameter search" or the "Aliens optimization" — its workings and requirements are described in greater detail [here](http://www.serbanology.com/article/The%20Trick%20From%20Aliens).

In short, we'll binary search for the largest per-path penalty \(P\) (between \(0\) and \(\sum_{i=1}^N C_i)\)) which results in an ore-nament count of \(o\) (excluding subtraction from path penalties) of at least \(K\). Note that \(o = x + p * P\). We can do so because:

  - As \(P\) increases, the path count \(p\) and corresponding ore-nament count \(o\) decrease or stays equal
  - If we define a function \(F(p)\) as the maximum ore-nament count \(o\) for a given path count \(p\), \(F(p)\) is concave (the more paths are used, the more diminished are their returns)

Let \(o_1\) and \(p_1\) be the optimal ore-nament and path counts for the penalty \(P\) produced by the binary search, and \(o_2\) and \(p_2\) be the corresponding counts for penalty \(P+1\). Note that \(o_2 \lt K \le o_1\) and \(p_2 \lt p_1\). The minimum number of paths required to collect \(K\) ore-naments is then somewhere in the interval \((p_2, p_1]\). In particular, we can linearly interpolate between \((o_1, p_1)\) and \((o_2, p_2)\) to compute our final answer as \(p_2 + \lceil(K - o_2)(p_1 - p_2) / (o_1 - o_2)\rceil + 1\).

The time complexity of this solution is \(O(N * \log(\sum_{i=1}^N C_i))\).


Code: #include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

const int LIM = 1000001;

int N;
long long K;
int C[LIM];
vector<int> ch[LIM];

// <sum, negative # of paths>
pair<long long, int> DP[LIM][3];            // [node][# of incoming paths]
pair<long long, int> DP2[3][2], nxt[3][2];  // [# of ongoing paths][counted node?]

void rec(int i, int p, long long P) {
  for (auto c : ch[i]) {
    rec(c, i, P);
  }
  memset(DP2, 0, sizeof DP2);
  DP2[1][1] = make_pair(C[i], 0);
  memcpy(nxt, DP2, sizeof nxt);
  for (auto c : ch[i]) {
    for (int j = 2; j >= 0; j--) {
      for (int b = 1; b >= 0; b--) {
        auto d = DP2[j][b];
        for (int j2 = 0; j2 <= 2; j2++) {
          auto d2 = DP[c][j2];
          for (int u = 0; u <= j2; u++) {
            int r = j2 - u;
            if (r > j) {
              continue;
            }
            int j3 = j + u - r;
            if (j3 < 0 || j3 > 2) {
              continue;
            }
            int b2 = b | (j2 ? 1 : 0);
            long long dv = d.first + d2.first + (!b && b2 ? C[i] : 0) - r * P;
            int dk = d.second + d2.second - r;
            nxt[j3][b2] = max(nxt[j3][b2], make_pair(dv, dk));
          }
        }
      }
    }
    memcpy(DP2, nxt, sizeof nxt);
  }
  for (int j = 0; j <= 2; j++) {
    for (int j2 = 0; j2 <= j; j2++) {
      int e = j - j2;
      for (int b : {0, 1}) {
        auto d = DP2[j][b];
        DP[i][j2] = max(DP[i][j2], make_pair(d.first - e * P, d.second - e));
      }
    }
  }
}

pair<long long, int> solve(long long P) {
  memset(DP, 0, sizeof DP);
  rec(0, -1, P);
  auto d = DP[0][0];
  return make_pair(d.first + -d.second * P, -d.second - 1);
}

int solve() {
  for (int i = 0; i < LIM; i++) {
    ch[i].clear();
  }
  // Input.
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    cin >> C[i];
  }
  for (int i = 1, j; i <= N - 1; i++) {
    cin >> j;
    ch[j - 1].push_back(i);
  }
  // Binary search for appropriate path penalty.
  long long r1 = -1, r2 = (long long)N * 1e9 + 1;
  while (r2 > r1) {
    long long m = (r1 + r2 + 1) >> 1;
    auto ans = solve(m);
    if (ans.first < K) {
      r2 = m - 1;
    } else {
      r1 = m;
    }
  }
  // Compute final answer.
  int ans = -1;
  if (r1 >= 0) {
    pair<long long, int> ans1 = solve(r1), ans2 = solve(r1 + 1);
    assert(ans2.first < K && K <= ans1.first && ans2.second < ans1.second);
    long long diffV = ans1.first - ans2.first;
    int diffK = ans1.second - ans2.second;
    long long need = K - ans2.first;
    ans = ans2.second + (need * diffK + diffV - 1) / diffV;
    assert(ans2.second < ans && ans <= ans1.second);
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}