Contest Duration: - (local time) (120 minutes) Back to Home
Official

## D - Zigzag Tree Editorial by evima

Let us choose the root arbitrarily so that the graph is rooted.

Assigning a permutation to the vertices can be rephrased into setting a total order on the vertices. The condition in question holds if and only if one of the following holds for any vertex $$v$$ (the inequality is regarding the total order):

• $$v > w$$ for any $$w$$ adjacent to $$v$$,
• $$v < w$$ for any $$w$$ adjacent to $$v$$.

Let us say a $$v$$ with the former property big, and a $$v$$ with the latter property small.

### ◆ Tree DP

For a rooted subtree with $$n$$ vertices rooted at $$v$$, let us call the following value $$\mathrm{dp}_v[i]$$.

• The number of ways to set a total order on the vertices in the rooted tree $$v$$ such that the root $$v$$ is small and the value assigned to the root is the $$i$$-th smallest value.

We can solve the problem by a tree DP that computes this from bottom to top. In this DP, we first need to merge the information from subtrees to compute the information for subforests in order.

For a forest with $$n$$ vertices, we compute the following for each $$i$$.

• The number of ways to set a total order on the vertices in the forest such that all roots are small and the maximum value assigned to the root is the $$i$$-th smallest value.

### ◆ Merging the DP table

We can see that computing the following is the key to the problem.

• We have a set $$A$$ with $$n$$ elements and a set $$B$$ with $$m$$ elements.
• $$\mathrm{dp}_A[i]$$ is given, which is the number of total orders on $$A$$ where the root is the $$i$$-th smallest and a certain requirement is satisfied. $$\mathrm{dp}_B[i]$$ is given similarly.
• Compute $$\mathrm{dp}[i]$$, the number of total orders on $$A\amalg B$$ where the restrictions on $$A$$ and $$B$$ satisfy the requirement and the larger of the roots of $$A$$ and $$B$$ is the $$i$$-th smallest.

We will divide the computation into two, based on which of the roots is larger.

Let us fix the order $$a_1 < a_2 < \cdots < a_n$$ on $$A$$ and the order $$b_1 < b_2 < \cdots < b_m$$ on $$B$$. When the root of $$A$$ is $$A_i$$, the number of ways to extend the orders so that $$a_i$$ is the $$(A\amalg B)$$-th smallest in $$A\amalg B$$ can be computed as the product of the following:

• setting the order between $$a_1,\ldots,a_{i-1}$$, $$b_1,\ldots,b_j$$: $$\binom{i-1+j}{i-1}$$ ways
• setting the order between $$a_{i+1},\ldots,a_n$$, $$b_{j+1},\ldots,b_m$$: $$\binom{n-i+m-j}{n-i}$$ ways

Additionally, $$a_i$$ is larger than the root of $$B$$ when the root of $$B$$ is one of $$b_1,\ldots,b_j$$. Thus, to $$\mathrm{dp}[i+j]$$, we will add $$\binom{i-1+j}{i-1}\binom{n-i+m-j}{n-i}\mathrm{dp}_A[i] (\mathrm{dp}_B[1]+\cdots+\mathrm{dp}_B[j])$$. After pre-calculation of prefix sums, this can be done in $$O(nm)$$ time in total.

### ◆ Complexity Analysis

In a tree DP, if merging the information of subforests of sizes $$n$$ and $$m$$ takes $$O(nm)$$ time, the information of the whole rooted tree with $$N$$ vertices can be computed in $$O(N^2)$$ time. The analysis of this complexity can be found, for example, on:

This analysis or tree DPs that involve it is often called “squared tree DP” in the Japanese kyo-pro community.

posted:
last update: