Problem: similar_ships (2023 round3)

The Flying Dutchman is making a killing giving out haunted house tours of his ghost ship. The ship has \(N\) cabins, numbered from \(1\) to \(N\), connected by corridors in the shape of an unrooted tree \(t_1\). For each \(i=2..N\), there is a corridor that connects cabin \(i\) to cabin \(P_{i}\).

Mr. Krabs noticed this business opportunity, and wants to make his own ship, also with \(N\) cabins, connected as a yet-to-be-determined tree \(t_2\). To avoid any lawsuits from the Dutchman, he would like to make his ship as different as possible.

In particular, let \(S(t)\) be the multiset of all subtrees of tree \(t\), where a subtree is any non-empty subset of cabins that are connected. For two multisets of trees \(S_1\) and \(S_2\), let \(\text{similarity}(S_1, S_2)\) be the number of trees in \(S_2\) that are [isomorphic](https://en.wikipedia.org/wiki/Graph_isomorphism) to at least one tree in \(S_1\). Note that \(\text{similarity}(S_1, S_2)\) and \(\text{similarity}(S_2, S_1)\) are not necessarily equal.

Help Mr. Krabs find the minimum possible value of \(\text{similarity}(S(t_1), S(t_2))\) over all trees \(t_2\) of size \(N\). As this value may be large, output it modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \leq T \leq 35\)
\(2 \leq N \leq 1{,}000{,}000\)
\(1 \leq P_i \leq N\)

The sum of \(N\) across all test cases is at most \(10{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. Each case has two lines. The first contains the integer \(N\), and the second contains the \(N-1\) integers \(P_2\) through \(P_N\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by the minimum possible similarity if \(t_2\) is chosen optimally, modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

The first sample case is depicted below. One possible tree that minimizes the similarity score is the same tree given in the input (i.e. choose \(t_2 = t_1\)). Then, \(S(t_2)\) consists of the \(6\) subtrees: \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1, 2\}\), \(\{2, 3\}\), and \(\{1, 2, 3\}\). Each subtree is isomorphic to a subtree of \(t_1\), so the similarity score is \(6\).

{{PHOTO_ID:720027639598818|WIDTH:280}}

In the second case, one possible \(t_2\) that minimizes the similarity score is depicted below. This tree has \(24\) different subtrees, of which \(21\) are isomorphic to a subtree of the given \(t_1\). For example, the subtree \(\{2, 3, 4, 6\}\) of this \(t_2\) is isomorphic to subtree \(\{2, 3, 4, 5\}\) of the given \(t_1\), but the subtree \(\{1, 2, 3, 6\}\) of this \(t_2\) is not isomorphic to any subtree of \(t_1\).

{{PHOTO_ID:854841726123175|WIDTH:350}}


Sample input:
2
3
1 2
6
1 2 3 4 5


Sample output:
Case #1: 6
Case #2: 21


Solution: Choosing a tree \(t_2\) that's a line (that is, \(N\) nodes connected as a chain\) always minimizes \(\text{similarity}(S(t_1), S(t_2))\).

Proof: Let \(t_\text{line}\) be a line of size-\(N\), and \(t_x\) be any tree of size \(N\). We'll show for any \(t_1\) and any \(t_x\), \(\text{similarity}(S(t_1), S(t_\text{line})) \le \text{similarity}(S(t_1), S(t_x))\)\). Let’s also not consider subtrees of size \(1\) (because all trees of size \(n\) have \(n\) subtrees of size \(1\)). There are two cases:

*Case 1*: Consider \(t_x\) such that \(\text{diameter}(t_x) \le \text{diameter}(t_1)\). We can choose any two nodes from \(t_x\) and get the path between them. This will be a subtree of \(t_1\). However, \(\text{similarity}(S(t_1), S(t_\text{line}))\) is at most \(\binom{n}{2}\), because \(S(t_\text{line})\) itself has only \(\binom{n}{2}\) elements.

*Case 2*: Consider \(t_x\) such that \(\text{diameter}(t_x) > \text{diameter}(t_1)\). For any pair of nodes \((u, v) \in t_x\), either the path from \(u\) to \(v\) is a subtree of \(t_1\), or there is a corresponding pair in \(t_\text{line}\) that is not a subtree of \(t_1\).

Therefore, \(\text{similarity}(S(t_1), S(t_\text{line})) \le \text{similarity}(S(t_1), S(t_x))\). To compute the former, simply calculate the diameter of \(t_1\) using two DFS's and use combinatorics. In particular, each length \(i\) line (of \(i + 1\) nodes) appears in \(S(t_\text{line})\) exactly \(N - i\) times, and all of these sub-lines are isomorphic to a subtree of \(t_1\). The answer will be:
\[ \sum_{i=0}^{\text{diameter}(t_\text{line})} N - i \]


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

const long long MOD = 1000000007;

int N;
vector<vector<int>> adj;

void dfs(int u, vector<bool>& visit, int& farthest, int& maxd, int d) {
  visit[u] = true;
  if (d > maxd) {
    farthest = u;
    maxd = d;
  }
  for (int v : adj[u]) {
    if (!visit[v]) {
      dfs(v, visit, farthest, maxd, d + 1);
    }
  }
}

int solve() {
  cin >> N;
  adj.assign(N, {});
  for (int i = 1, p; i < N; i++) {
    cin >> p;
    p--;
    adj[i].push_back(p);
    adj[p].push_back(i);
  }
  vector<bool> visit(N, false);
  int farthest = 0, diameter = 0;
  dfs(0, visit, farthest, diameter, 0);
  visit.assign(N, false);
  dfs(farthest, visit, farthest, diameter, 0);
  int ans = 0;
  for (int i = 0; i <= diameter; i++) {
    ans = (ans + (N - i)) % MOD;
  }
  return ans;
}

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