Editorial for Tree Royale

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Parsa

Let the tree whose root is not connected to any other tree be denoted by $R$ ~R~.
It is clear that such a tree will always exist.

Step 1 - Using All Trees in the Diameter

It is evident that the optimal answer will always include all trees that lie along the diameter of the combined structure.
Reason: Suppose a tree is not part of the diameter. Then we could detach that tree from its current position and connect its root to one of the endpoints of the current diameter, thereby increasing the overall diameter - a contradiction.

Also note that this particular tree $R$ ~R~ cannot be part of the diameter.

Step 2 - Contribution of Each Tree

For each tree:

If it is not $R$ ~R~, it contributes to the diameter with the longest path from its root to one of its leaves.
If it is $R$ ~R~, it contributes with its full diameter.

Why?

For non- $R$ ~R~ trees, the connecting point is the root, so only the longest root-to-leaf path is relevant.
For $R$ ~R~, since it is an independent tree, its full diameter can appear in the final diameter path.

Step 3 - Definitions

Let:

$P_i$ ~P_i~ = diameter of tree $T_i$ ~T_i~.
$D_i$ ~D_i~ = longest path length from the root of $T_i$ ~T_i~ to any of its leaves.

Step 4 - Computing the Final Diameter

Let the final diameter length be $S$ ~S~.
It can be shown that:

$S = \max_{1 \le i, j \le n} \Big( \sum_{i=1}^n P_i - P_j + D_j \Big) + (n - 1)$

where:

Index $j$ ~j~ is the choice of the special tree $R$ ~R~. We add $n - 1$ ~n - 1~ to account for the edges introduced when joining the $n$ ~n~ individual trees into a single connected structure. Each connection between two trees adds exactly one edge, and connecting $n$ ~n~ trees requires $n - 1$ ~n - 1~ such edges. Once all $P_i$ ~P_i~ and $D_i$ ~D_i~ are computed, this expression can be evaluated efficiently.

C++ Solution:

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define fr first
#define sc second

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;


const int MAXN = 1e6 + 16, MAXM = 1e2 + 10;

int n;
vector <int> adj[MAXN];
int mxh[MAXN], d;

void DFS(int v) {
  int mx1 = 0, mx2 = 0;
  for (auto u: adj[v]) {
    DFS(u);
    mxh[v] = max(mxh[v], mxh[u] + 1);
    if (mxh[u] + 1 > mx1) mx2 = mx1, mx1 = mxh[u] + 1;
    else if (mxh[u] + 1 > mx2) mx2 = mxh[u] + 1;
  }
  d = max(d, mx1 + mx2);
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  int tt;
  cin >> tt;
  while (tt--) {
    int m;
    cin >> m;
    int sm = 0, mx = 0;
    for (int t = 0; t < m; t++) {
      cin >> n;
      for (int i = 0; i < n; i++) adj[i].clear();
      for (int i = 0; i < n; i++) mxh[i] = 0;
      d = 0;
      for (int i = 1, p; i < n; i++) {
    cin >> p;
    adj[--p].pb(i);
      }
      DFS(0);
      sm += mxh[0];
      mx = max(mx, d - mxh[0]);
    }
    cout << sm + mx + m - 1 << endl;
  }
  return 0;
}

Python solution:

import sys, io
input = sys.stdin.readline

adj = []
max_heights = []
diameter = 0

def dfs(v):
    global adj, max_heights, diameter
    # Diameter is the sum of the highest two depths, we can store both
    mh = mh2 = 0

    for u in adj[v]:
        dfs(u)
        max_heights[v] = max(max_heights[v], max_heights[u]+1) # 1+childs height

        # Maintain highest and second highest height
        if (max_heights[u]+1 > mh):
            mh2 = mh
            mh = max_heights[u]+1
        elif (max_heights[u]+1 > mh2):
            mh2 = max_heights[u]+1

    # Maintain max diameter as sum of the two highest heights in the tree
    diameter = max(diameter, mh+mh2)



t = int(input())

# For each test case
for _ in range(t):
    n = int(input()) # Number of trees

    total_heights = 0 # All trees besides one will contribute their max height
    max_diameter = 0  # A single tree will contribute its diameter as root, we store the max one

    for _ in range(n):
        m = int(input()) # Vertices of current tree

        adj = [[] for _ in range(m)]
        max_heights = [0 for _ in range(m)]
        diameter = 0

        parents = [int(x) for x in input().split()]
        for i in range(1, m):
            adj[parents[i-1]-1].append(i)

        dfs(0)
        total_heights += max_heights[0]

        # The tree that contributes its diameter doesn't contribute its height,
        # so we offset that here
        max_diameter = max(max_diameter, diameter-max_heights[0])

    # n-1 new edges are formed from merging the trees
    print(max_diameter + total_heights + n - 1)

Comments

There are no comments at the moment.