Problem: quarantine (2020 round1)

Let's give it up for all the health care professionals working on the front lines in the face of the COVID-19 pandemic. Many of them can be found at the Stanford-Sunnyvale Teaching Hospital (SSTH), a facility that's working tirelessly to keep the disease under control. The hospital is already following standard infection prevention and control practices, but Dr. Gregory Klaus, M.D. (one of SSTH's most brilliant doctors) is hoping to further reduce transmissions by making some renovations to the building layout.

A certain floor of the SSTH facility features \(N\) rooms (numbered from \(1\) to \(N\)) and \(N - 1\) hallways (each running directly between a pair of rooms), such that every room is reachable from every other room through a sequence of hallways. In computer science terms, the floor is organized like a tree rooted at room 1. Specifically, for each room \(i\) aside from the first (\(2 \le i \le N)\), there's a hallway running between it and room \(E_i\) that can be traversed in either direction.

Each room \(i\) contains either a patient that has been diagnosed with COVID-19 (denoted by \(S_i\) = _"#"_), or otherwise an uninfected patient (denoted by \(S_i\) = _"*"_).

With the help of the hospital's construction team, Dr. Klaus plans to renovate the floor as follows: close down one existing hallway and then construct a new one between two rooms, such that all rooms on the floor still end up reachable from all other rooms. In doing so, he would like to maximize the number of unordered pairs of uninfected patients who can safely reach each other in the resulting layout. An uninfected patient can safely reach another uninfected patient if their rooms are connected by a sequence of hallways which doesn't pass through any rooms with infected patients. It's possible that Dr. Klaus may elect to close down a hallway and then reconstruct a hallway between that same pair of rooms — the renovation budget needs to go somewhere...

For example, consider the following floor layout, with rooms 2 and 6 containing infected patients:

{{PHOTO_ID:729459790952901}}
  
Initially, only the uninfected patients in rooms 1 and 3 can safely reach each another. However, if Dr. Klaus were to close down the hallway between rooms 1 and 2 and construct a new one between rooms 1 and 5 (as illustrated below), then patients in any of the three pairs of rooms (1, 3), (1, 5), and (3, 5) would be able to reach one another:
  
{{PHOTO_ID:294725001615446}}

Klaus has just two questions: what is the maximum attainable number of such safely-reachable uninfected patient pairs, and what is the number of distinct ordered pairs of hallway closures/constructions yielding that result?

In order to reduce the size of the input, the values \(E_{2..N}\) will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(E_{2..(K+1)}\), as well as the 3 constants \(A\), \(B\), and \(C\), and must then compute the remaining values \(E_{(K+2)..N}\) as follows:

\(E_i = ((A * E_{i-2} + B * E_{i-1} + C) \text{ modulo } (i - 1)) + 1\) for \(i > K+1\)

# Input

Input begins with an integer \(T\), the number of hospital floors. For each floor, there are 4 lines. 

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

The second line contains the length-\(N\) string \(S_{1..N}\).

The third line contains the \(K\) space-separated integers \(E_{2..K+1}\).

The fourth line contains the 3 space-separated integers \(A\), \(B\), and \(C\).

# Output

For the \(i\)th hospital floor, print a line containing *"Case #i: "* followed by 2 integers, the maximum attainable number of safely-reachable uninfected patient pairs, and the number of distinct renovation plans yielding that result.

# Constraints

\(1 \le T \le 80\) 
\(3 \le N \le 1,000,000\)
\(2 \le K \le N-1\)
\(S_i \in \{``*", ``\#"\}\)
\(0 \le A, B, C \le 1,000,000,000\)
\(1 \le E_i \le i-1\)

The sum of N across all floors is at most 4,000,000.

# Explanation of Sample

For the first floor, any of the following four renovation plans would result in every uninfected patient being able to safely reach every other uninfected patient (for a total of 3 pairs):

  - Close hallway 1-2, construct hallway 1-2
  - Close hallway 1-2, construct hallway 1-3
  - Close hallway 2-3, construct hallway 1-3
  - Close hallway 2-3, construct hallway 2-3

For the second floor, the same four renovation plans would all result in 0 safely-reachable uninfected patient pairs, while still ensuring that all rooms remain reachable from all other rooms.

For the third floor, only the following two renovation plans would allow the two uninfected patients to safely reach one another:

  - Close hallway 1-2, construct hallway 2-3
  - Close hallway 1-3, construct hallway 2-3
  
The fourth floor is illustrated above, including one of eight optimal renovation plans for it.

For the sixth floor, \(E_{2..N} = [1, 2, 2, 4, 3, 6, 4, 8, 5]\).


Sample input:
6
3 2
***
1 2
0 0 0
3 2
###
1 2
0 0 0
3 2
#**
1 1
0 0 0
6 5
*#***#
1 1 2 2 3
0 0 0
5 4
**##*
1 1 2 2
0 0 0
10 2
**#*#***#*
1 2
3 4 5


Sample output:
Case #1: 3 4
Case #2: 0 4
Case #3: 1 2
Case #4: 3 8
Case #5: 3 12
Case #6: 15 16


Solution: We'll define a "region" as a set of _"*"_ nodes reachable from one another without passing through _"#"_ nodes, and the size of a region as the number of nodes in it. We'll then let \(C_i\) be the size of node \(i\)'s region (with \(C_i = 0\) if \(S_i\) = _"#"_). The regions and \(C\) values may all be computed in \(O(N)\) time using floodfill (DFS). We can also compute the initial number of safely-reachable node pairs — each region having size \(s\) contributes \(s(s-1)/2\) such pairs.

We'll consider each non-root node \(i\) such that the edge between \(i\) and \(E_i\) will be deleted. For now, we'll ignore the case in which there are fewer than two regions, and return to it later. When there are at least two regions, we should only consider edges that won't break up a region (that is, nodes \(i\) such that \(S_i\) = _"#"_ and/or \(S_{E_i}\) = _"#"_). Let's say that the maximum \(C\) value within \(i\)'s subtree is \(m_1\), and there are \(q_1\) nodes in \(i\)'s subtree with that \(C\) value. Let's similarly define \(m_2\) and \(q_2\) for nodes outside \(i\)'s subtree. An edge insertion can then contribute up to \(m_1 m_2\) additional safely-reachable node pairs on top of the initial number, and there are \(q_1 q_2\) edge insertions for which that's the case.

Returning to the case in which there's at most one region, essentially the only difference is that we may consider deleting any edge. If we delete one between two _"*"_ nodes (thus breaking up the single region), we must ensure that an edge is then inserted between two nodes with non-zero \(C\) values (very similar to the above, except noting that there will be no additional safely-reachable node pairs on top of the initial number). If we delete a different edge, then *any* edge may be inserted (between a node within \(i\)'s subtree and a node outside it).

Each of the values required above (such as \(m_1\), \(q_1\), \(m_2\), and \(q_2\)) may be obtained in constant time after a \(O(N)\) precomputation process. In particular, we'll begin by performing a pre-order traversal of the tree while numbering the nodes in that order and storing the range of nodes included in each node's subtree (which must be a contiguous subarray of this ordering). Then, for each prefix and suffix of this ordering, as well as for each subtree's subarray, we'll compute two values: the maximum \(C\) value present amongst those nodes, and the number of those nodes having that \(C\) value.

As such, the time complexity of this solution comes out to \(O(N)\).


Code: // Quarantine
// 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 1000001
#define MOD 1000000007

#define MCPR pair<LL,LL>

int N, K, A, B;
char S[LIM];
int E[LIM], C[LIM];
int pi, P[LIM], L[LIM], R[LIM];
vector<int> ch[LIM];
MCPR preM[LIM], sufM[LIM], subM[LIM];

void ReadSeq(int* V, int N, int K)
{
  int i, A, B, C;
  Fox1(i, K)
    Read(V[i]);
  Read(A), Read(B), Read(C);
  FoxI(i, K + 1, N - 1)
    V[i] = ((LL)A * V[i - 2] + (LL)B * V[i - 1] + C) % i + 1;
}

// traverses the tree in pre-order, numbering nodes and storing their subtrees' ranges
void Pre(int i)
{
  P[pi] = i;
  L[i] = pi++;
  for (auto j : ch[i])
    Pre(j);
  R[i] = pi - 1;
}

// returns number of "*" nodes reachable from i in its subtree
int CountC(int i)
{
  if (S[i] == '#')
    return(0);
  int c = 1;
  for (auto j : ch[i])
    c += CountC(j);
  return(c);
}

// sets C values of all "*" nodes reachable from i in its subtree
void SetC(int i, int c)
{
  if (S[i] == '#')
    return;
  C[i] = c;
  for (auto j : ch[i])
    SetC(j, c);
}

// combines two max/count pairs
MCPR Comb(MCPR a, MCPR b)
{
  LL m = max(a.x, b.x);
  return(mp(m, (a.x == m ? a.y : 0) + (b.x == m ? b.y : 0)));
}

MCPR ProcessCase()
{
  int i, j;
  // init
  Fill(C, 0);
  Fox(i, N)
    ch[i].clear();
  // input, and generate E values
  Read(N), Read(K);
  scanf("%s", &S);
  ReadSeq(E, N, K);
  Fox1(i, N - 1)
  {
    E[i]--;
    ch[E[i]].pb(i);
  }
  // number nodes in pre-order
  pi = 0;
  Pre(0);
  // floodfill to find connected * regions
  int nr = 0;
  LL base = 0;
  Fox(i, N)
    if (S[i] == '*' && !C[i])
    {
      nr++;
      int c = CountC(i);
      SetC(i, c);
      base += (LL)c * (c - 1) / 2;
    }
  // precompute prefix, suffix, and subtree C value max/count pairs
  preM[0] = sufM[N] = mp(-1, 0);
  Fox(i, N)
    preM[i + 1] = Comb(preM[i], mp(C[P[i]], 1));
  FoxR(i, N)
  {
    sufM[i] = Comb(sufM[i + 1], mp(C[P[i]], 1));
    subM[i] = mp(C[i], 1);
    for (auto j : ch[i])
      subM[i] = Comb(subM[i], subM[j]);
  }
  // consider each possible edge to delete
  MCPR ans = mp(-1, 0);
  Fox1(i, N - 1)
    if (S[i] == '#' || S[E[i]] == '#' || nr == 1)
    {
      // compute max/count pairs inside/outside i's subtree
      MCPR in, out;
      if (nr == 1 && (S[i] == '#' || S[E[i]] == '#'))
      {
        // max values are irrelevant in this case
        in = mp(0, R[i] - L[i] + 1);
        out = mp(0, N - in.y);
      }
      else
      {
        in = subM[i];
        out = Comb(preM[L[i]], sufM[R[i] + 1]);
      }
      MCPR cur = mp(base, in.y * out.y);
      if (nr > 1)
        cur.x += in.x * out.x;
      ans = Comb(ans, cur);
    }
  return(ans);
}

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