Problem: running_on_fumes_ch2 (2020 quals)

**Note: This problem shares similarities with [Chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2020/qualification-round/problems/D1). The solution to either chapter may help with solving the other, so please consider reading both first.**

After working for many months as a delivery driver for a nationwide supply chain, you've finally received a promotion! This promotion has come with a nice pay bump, but also with the responsibility of serving regions with more complex maps. With no opportunity for a vacation, you've promptly been assigned a new series of long-haul jobs.

For each job, you will be provided with a map of the relevant region, which includes \(N\) cities (numbered from \(1\) to \(N\)) and \(N-1\) two-way roads running amongst them. In computer science terms, **the map is organized like a tree rooted at city 1**, such each city \(i\) is connected to its parent city \(P_i\) by a road (aside from city 1, which has no parent, with \(P_1\) given as 0). It's possible to drive from any city to any other city by following a sequence of roads. Note that each road may be driven along in either direction (either from city \(i\) to city \(P_i\), or vice versa).

You will begin in a given city \(A\) with a shipment of supplies to be delivered to another given city \(B\), and with a full gas tank having a capacity of \(M\) gallons. You will then have two options at each point in time:

  1. Drive along a road from your current city to an adjacent one, using up 1 gallon of gas. You may not do this if your tank is empty, but it's fine if your tank becomes empty as a result.
  2. Fill your tank all the way back up to \(M\) gallons of gas at a cost of \(C_i\) dollars, where \(i\) is your current city. Note that the cost is independent of how much gas your tank had before refueling. You may not do this if city \(i\) has no gas station (indicated with \(C_i\) = 0).

Determine the minimum cost required to complete your delivery, if it's possible at all.

# Input

Input begins with an integer \(T\), the number of long-haul jobs you are assigned. For each job there is first a line containing the space-separated integers \(N\), \(M\), \(A\), and \(B\). Then, \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(P_i\) and \(C_i\).

# Output

For the \(i\)th job, output a line containing *"Case #i: "* followed by a single integer, the minimum cost in dollars to get from city \(A\) to city \(B\), or \(-1\) if it's impossible.

# Constraints

\(1 \le T \le 80\)
\(2 \le N \le 1,000,000\)
\(1 \le M \le N\)
\(1 \le A, B \le N\)
\(A \ne B\)
\(0 \le P_i \le N\)
\(0 \le C_i \le 1,000,000,000\)

The sum of \(N\) across all jobs is at most 3,000,000.

# Explanation of Sample

The regional map for the first job looks as follows:

{{PHOTO_ID:781032149369958}}
 
You will begin in city 2 with 1 gallon of gas. The cheapest strategy involves driving to city 4, refueling there for a cost of $40, and then driving onwards to city 3.

The regional map for the next 3 jobs looks as follows, such that you need to drive from city 5 to city 3:

{{PHOTO_ID:412634646784856}}

In the second job, your gas tank has a capacity of 1 gallon. No matter what you do, you will deplete all of your gas in the drive from city 8 to city 6, where there will be no way to refuel and proceed to eventually reach city 3.

In the third job, your gas tank has a capacity of 2 gallons. The cheapest strategy involves refueling at both cities 8 and 1 on the way to city 3, costing a total of $30 + $30 = $60.

In the fourth job, your gas tank has a capacity of 3 gallons. This isn't quite enough to drive all the way to city 3 without refueling. The cheapest strategy involves depleting all of your gas to drive through cities 8 and 6 to city 7, refueling there for $20, and then depleting all of your gas to drive through cities 6 and 1 to reach city 3.


Sample input:

Sample output:


Code: // Running on Fumes - Chapter 2
// 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 <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);
}

#define LIM 1000008
#define LIM2 2100000

int N, M, A, B;
vector<int> con[LIM];
int P[LIM], C[LIM];
int mZ, mD, mHas[LIM], mC[LIM];
int sz;
LL tree[LIM2];

// DFS from node i, while populating parents
void rec1(int i)
{
  int j, c;
  Fox(j, Sz(con[i]))
    if ((c = con[i][j]) != P[i])
    {
      P[c] = i;
      rec1(c);
    }
}

// DFS from node i, with depth d and previous node p, while populating min. C values per depth
void rec2(int i, int d, int p)
{
  int j, c;
  if (C[i])
  {
    Max(mD, d);
    if (mHas[d] == mZ)
      Min(mC[d], C[i]);
    else
      mHas[d] = mZ, mC[d] = C[i];
  }
  Fox(j, Sz(con[i]))
    if ((c = con[i][j]) != P[i])
      if (c != p)
        rec2(c, d + 1, p);
}

// update value at index i in segment tree to be at most v
void Update(int i, LL v)
{
  i += sz;
  while (i)
  {
    Min(tree[i], v);
    i >>= 1;
  }
}

// query min. value in segment tree within indices [a, b]
LL Query(int i, int r1, int r2, int a, int b)
{
  if (a <= r1 && r2 <= b)
    return(tree[i]);
  i <<= 1;
  int m = (r1 + r2) >> 1;
  LL ret = (LL)INF * INF;
  if (a <= m)
    Min(ret, Query(i, r1, m, a, b));
  if (b > m)
    Min(ret, Query(i + 1, m + 1, r2, a, b));
  return(ret);
}

LL ProcessCase()
{
  int i, j, k, p, d;
  // input
  Read(N), Read(M), Read(A), Read(B);
  Fox1(i, N)
  {
    Read(j), Read(C[i]);
    if (j)
    {
      con[i].pb(j);
      con[j].pb(i);
    }
  }
  // root tree at B
  P[B] = -1;
  rec1(B);
  // init segment tree of min. costs
  Fill(tree, 60);
  for (sz = 1; sz < N; sz <<= 1);
  // iterate along path from A to B while maintaining segment tree
  Update(0, 0);
  for (p = A, i = P[A], k = 1; i != B; p = i, i = P[i], k++)
  {
    // explore branches off of main path
    mZ++, mD = -1;
    rec2(i, 0, p);
    // consider refueling here or within an attached branch
    Fox(d, mD + 1)
      if (k - d >= 0 && mHas[d] == mZ)
      {
        LL m = Query(1, 0, sz - 1, max(0, k - (M - d)), k);
        Update(k - d, m + mC[d]);
      }
  }
  // clear graph
  Fox1(i, N)
    con[i].clear();
  // get answer
  LL ans = Query(1, 0, sz - 1, max(0, k - M), k - 1);
  return ans >= (LL)INF * INF ? -1 : ans;
}

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