Problem: wiki_race (2023 round2)

You and some friends are playing [Wiki Race](https://en.wikipedia.org/wiki/Wikipedia:Wiki\_Game) on an online encyclopedia of \(N\) pages, numbered from \(1\) to \(N\). Page \(i\) covers \(M_i\) topics \(S_{i,1}\) ... \(S_{i,M_i}\), each a string of lowercase letters. Each player starts on a unique page, and will race to reach page \(1\) (the target page) by repeatedly clicking to neighboring pages.

Unfortunately, someone out there has already published the shortest path from each page to page \(1\) for the whole internet to see. This forms a tree structure with page \(1\) as the root, and edges directed upwards from each descendent page. In particular, you and your friends all know that at each page \(i > 1\), one should click to the neighboring page \(P_i\) for the fastest route to page \(1\).

In light of this, all players have agreed to a new rule that each page should be visited by exactly one person per game. This means that once a player hits a page someone has already visited, their upward path ends there and the player loses. Formally, we can express each game's outcome as a partition of the tree into vertex-disjoint paths, with each path's upper endpoint always having an edge to a node on another player's path (except the winner, whose upper endpoint is page \(1\)).

After playing the game for so long, you're all starting to realize that "*it's not about winning, but the knowledge acquired along the way!*" 

For a given partition of the tree into paths, a topic is _mutually-learned_ by all players if every path has at least one page covering that topic. You'd like to know, across all possible partitions of paths, all topics that could be mutually-learned.


# Constraints

\(1 \leq T \leq 30\)
\(2 \leq N \leq 1{,}000{,}000\)
\(1 \leq P_i \leq N\)
\(1 \leq M_i \leq 100{,}000\)
\(1 \leq |S_{i,j}| \leq 10\)
\(S_{i,j}\) consists only of lowercase letters ('`a`'..'`z`').
The sum of \(N\) across all test cases is at most \(3{,}000{,}000\).
The sum of \(M_i\) across all test cases is at most \(8{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing \(N - 1\) integers \(P_2, ..., P_N\). Then, \(N\) lines follow, the \(i\)th of which contains the integer \(M_i\), followed by strings \(S_{i,1}\) ... \(S_{i,M_i}\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by the number of topics that can be mutually-learned.


# Sample Explanation

The three sample cases are depicted below:

{{PHOTO_ID:636025968710743|WIDTH:600}}
 
In the first case:
* "gouda" is mutually-learned in the partition \(\{\{4\}, \{6, 5, 2\}, \{3, 1\}\}\)
* "cheddar" is mutually-learned in the partition \(\{\{4, 2\}, \{6, 5\}, \{3, 1\}\}\)
* "edam" is mutually-learned in the same partition as "cheddar" as well as in other partitions such as \(\{\{4, 2, 1\}, \{6\}, \{5\}, \{3\}\}\)
* "gjetost", "gruyere", and "mozzarella" can never be mutually-learned

In the second case, the only topic that can be mutually-learned is "earth".

In the third case, the partition \(\{\{1, 2, 3\}\}\) makes all three topics mutually-learned.



Sample input:
3
6
1 1 2 2 5
4 mozzarella cheddar gouda edam
5 gouda gjetost mozzarella cheddar edam
3 gruyere mozzarella edam
1 gouda
1 edam
3 cheddar gruyere edam
4
1 2 2
2 earth water
2 wind wind
2 earth fire
2 light metal
3
1 2
1 a
1 b
1 c


Sample output:
Case #1: 3
Case #2: 1
Case #3: 3


Solution: Let \(L\) be the number of leaves in the tree. A partition that optimally learns topics for all players might as well start each player's path from a leaf. Therefore there can be at most \(L\) paths to consider in a given partition.

Let \(F(s)\) be the frequency of topic \(s\) in the input. If a topic \(s\) is mutually-learnable, then it must be that \(F(s) \ge L\). This means there can be at most \(\mathcal{O}((\sum M_i) / L)\) candidate words. Assuming we have an \(\mathcal{O}(L)\) algorithm to verify that a candidate word is mutually-learnable, then we would have an overall running time of \(\mathcal{O}((\sum M_i) / L) * \mathcal{O}(L) = \mathcal{O}(\sum M_i)\), which is sufficient.

We can compress the tree by merging "lines", or sequences of nodes with only one child each. This can be done with a DFS, where if we reach a node \(u\) with \(1\) child, we repeatedly "reel up" the single-child chain (merging the topic lists into node \(u\)), Once the last single-child's children has become \(u\)'s children, we branch out from \(u\).

With this compression, we guarantee that each tree node has at least \(2\) children. This means that the numbers of nodes at each level from the bottom to the root will be limited by \(L\), \(\frac{L}{2}\), \(\frac{L}{4}\), …, \(1\). The total sum of this geometric series, as we should know, is \(\mathcal{O}(L)\).

To check each candidate word, we can do a DFS on the compressed tree, resolving the problem bottom-up. If we find the string in the root of the subtree, we pair it with any leaf needing it. However, if at any time a subtree has two leaves or more with no matches, that topic can’t be mutually-learned.


Code: #include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int N, leaves;
vector<vector<int>> ch;
vector<unordered_set<string>> S(N);

// Collapse nodes with 1 ch, u->v->(w1,w2,...) into u->(w1, w2, ...).
void dfs1(int u) {
  if (ch[u].empty()) {
    leaves++;
    return;
  }
  while (ch[u].size() == 1) {
    int v = ch[u][0];
    S[u].insert(S[v].begin(), S[v].end());
    ch[u] = ch[v];
  }
  for (int v : ch[u]) {
    dfs1(v);
  }
}

int dfs2(int u, const string &s) {
  if (ch[u].empty()) {
    return S[u].count(s);
  }
  int has = 0;
  for (int v : ch[u]) {
    int res = dfs2(v, s);
    if (res == -1) {
      return -1;
    }
    has += res;
  }
  if (has == (int)ch[u].size()) {
    return 1;
  }
  if (has + 1 == (int)ch[u].size()) {
    return S[u].count(s);
  }
  return -1;
}

int solve() {
  cin >> N;
  ch.assign(N, {});
  S.assign(N, {});
  for (int i = 1, p; i < N; i++) {
    cin >> p;
    ch[p - 1].push_back(i);
  }
  unordered_map<string, int> freq;
  for (int i = 0, m; i < N; i++) {
    cin >> m;
    string s;
    for (int j = 0; j < m; j++) {
      cin >> s;
      S[i].insert(s);
      freq[s]++;
    }
  }
  // Collapse any single child chains in the tree, and count leaves.
  leaves = 0;
  dfs1(0);
  // Try all words with freq[k] >= L (there can only be O(W/L).
  int ans = 0;
  for (const auto &[s, f] : freq) {
    if (f >= leaves && dfs2(0, s) == 1) {
      ans++;
    }
  }
  return ans;
}

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