PERMATCH - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming, Combinatorics

PROBLEM:

Given N, a tree on N vertices is constructed as follows:

  • Choose a random array P of length N-1 such that 1 \le P_i \le i
  • Then, for each i = 2, 3, \ldots, N, add an edge between i and P_i.

Find the probability that the constructed tree has a perfect matching.

EXPLANATION:

The given process of building a tree can be thought of as follows:

  • Start with a single vertex labelled 1.
  • Then, for each i = 2, 3, \ldots, N in order, attach a vertex labelled i as the child of some vertex with smaller label (hence making it a leaf).

There are exactly (N-1)! labelled trees that can be created this way, so to compute the required probability, we can instead just count the number of such labelled trees that do have a perfect matching, and divide that by (N-1).

We’ll call trees built this way increasing trees, since labels are increasing on any downward path from the root.

First, let’s understand when a tree has a perfect matching.

One algorithm for that is as follows.
Consider the root, 1. Let its children be c_1, c_2, \ldots, c_k.
The root must be matched to some child, without loss of generality let it be c_1.
Then,

  • For each of c_2, c_3, \ldots, c_k, the subtree rooted at this child must be solved independently.
    This means each of these subtrees must themselves have perfect matchings.
  • For c_1, it’s matched to 1, so it cannot match to any of its children.
    Thus, all the children of c_1 must then have their subtrees solved independently.
    This means that the subtree of c_1 must have a perfect matching if c_1 is deleted from it.

This gives us a recursive procedure - match the root to one of its children, and then recursively solve for the subtrees obtained.

The main question is - which child should match the root?
The answer to that ends up being quite simple, actually.
Observe that a necessary (though not sufficient) condition for a tree to have a perfect matching, is that is must have an even number of vertices. This is, of course, because a matching pairs vertices.
Further, the matched child must satisfy “this subtree has a matching excluding its root”, which in turn is only possible when it has an odd number of vertices.

So, the root must have exactly one child subtree with odd size - and it will match to exactly this child. In any other case, a matching cannot exist since some subtree will end up failing the parity check.
This must then carry on recursively to the obtained smaller trees.
(Note that this also proves that the perfect matching, if it exists, is unique.)

Let’s use the above idea to build a solution.

Define a function f(i) as follows:

  • If i is even, f(i) is the number of increasing trees on i vertices that admit a perfect matching.
  • If i is odd, f(i) is the number of increasing trees on i vertices that admit a perfect matching, if the root is removed.

First, let’s look at the case where i is odd.
If i = 1 then f(1) = 1, so let’s look at i \gt 1.
Clearly, vertex 2 has to be a child of 1.
So, let’s consider the subtree of vertex 2. Suppose it has size 2s (since it must have a perfect matching, it has to be even).
Then,

  • There are \binom{i-2}{2s-1} ways to choose the vertices in this subtree: we can choose any 2s-1 vertices to include in it other than 1 and 2.
  • With the 2s chosen labels, the formed tree must be increasing and also have a perfect matching.
    There are f(2s) ways to achieve that.
  • With this subtree accounted for, the remaining i-2s vertices then need to themselves form a tree of size i-2s which admits a perfect matching with the root deleted.
    There are f(i-2s) ways to do this.

So, when i is odd, we simply obtain

f(i) = \sum_{2 \le 2s \lt i} \binom{i-2}{2s-1} \cdot f(2s) \cdot f(i-2s)

Next, consider even i.
Once again, 2 must be a child of 1, so we look at the subtree rooted at 2.
Let its size be s - this time, s can be even or odd.
Similar analysis shows that:

  • There are \binom{i-2}{s-1} ways to choose the labels of vertices in the subtree.
  • If s is even, the subtree must have a perfect matching (which has f(s) possibilities).
    Then, the remaining i-s vertices must form a tree with a perfect matching too, for f(i-s) ways.
  • If s is odd, 2 must be matched to 1, so the subtree of 2 must have a perfect matching with 2 excluded. This has f(s) possibilities.
    This then makes i-s be odd; and since 1 can’t match any of its remaining children, we’re just looking for trees with size i-s that have a perfect matching excluding the root, which has f(i-s) possibilities.

So, in either case, we obtain

f(i) = \sum_{1 \le s \lt i} \binom{i-2}{s-1} \cdot f(s) \cdot f(i-s)

Thus, the even and odd cases for computing f(i) are pretty much the same: just that in the odd case we restrict ourselves to even subtree sizes.

Observe that each f(i) can be computed in \mathcal{O}(i) time.
This allows for a solution in \mathcal{O}(N^2) time, which is fast enough for the given constraints as long as binomial coefficients are computed in constant time.

The final answer is f(N) if N is even, and 0 if N is odd.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

	const int mod = 998244353;
	auto modpow = [&] (int a, int n) {
		int r = 1;
		while (n) {
			if (n & 1) r = 1ll*r*a % mod;
			a = 1ll*a*a % mod;
			n /= 2;
		}
		return r;
	};
	const int N = 1e5 + 10;
	vector<int> fac(N, 1);
	for (int i = 2; i < N; ++i) fac[i] = 1ll*i*fac[i-1] % mod;
	auto inv = fac;
	for (int i = 2; i < N; ++i) inv[i] = modpow(fac[i], mod-2);
	auto C = [&] (int n, int r) {
		if (n < r or r < 0) return 0;
		int res = (1ll * fac[n] * inv[r]) % mod;
		res = (1ll * res * inv[n-r]) % mod;
		return res;
	};

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        
		vector dp(n+1, 0);
		dp[1] = 1;
		for (int i = 2; i <= n; ++i) {
			for (int s = i-1; s >= 1; s -= (1 + i%2)) {
				int ways = (1ll * dp[s] * dp[i-s]) % mod;
				dp[i] = (dp[i] + 1ll * ways * C(i-2, s-1)) % mod;
			}
		}

		if (n%2 == 0) cout << (1ll * dp[n] * inv[n-1]) % mod << '\n';
		else cout << 0 << '\n';
    }
}