Chain Prefix Rank (Easy Version)

Turn ranks into intervals

The first trap is thinking about the actual values $1,2,\dots,n$. Do not. The only thing that matters is the relative order of vertices by increasing $p_v$.

For a vertex $u$, $a_u$ says: among the ancestors of $u$, exactly $a_u$ are before $u$ in this order. So if the ancestors of $u$ are already sorted by their values, then $u$ must be inserted at position $a_u$ in that sorted list.

During a DFS of the original rooted tree, keep a vector chain: the current root-to-parent path, sorted by value order forced by the ranks so far. When visiting $u$:

• the predecessor of $u$ is chain[a[u]-1], or a left sentinel $0$ if $a_u=0$;
• the successor of $u$ is chain[a[u]], or a right sentinel $n+1$ if $a_u$ is the current chain length.

Call them $L_u$ and $R_u$. Then $u$ is directly inserted into the interval $(L_u,R_u)$, meaning

$L_u < u < R_u$

in the final value order.

After recording that interval, insert $u$ into chain at position $a_u$, DFS its children, then erase it. Since $n \le 5000$, vector insertion/erasure is totally fine: $O(n^2)$ worst case.

Why immediate intervals are enough

Suppose the ancestor list around $u$ looks like

$\dots, L_u, u, R_u, \dots$

after inserting $u$. All ancestors before $L_u$ are already less than $L_u$, hence less than $u$. All ancestors after $R_u$ are already greater than $R_u$, hence greater than $u$. So forcing only the two neighboring inequalities $L_u<u<R_u$ also forces the correct comparison against every ancestor. Nice, no need to dump all ancestor edges like a brute-force goblin. Actually wait, no goblins. Like a brute-force spreadsheet from hell.

So the problem becomes: count the total orders satisfying all these interval constraints.

The interval DP

Let $B(L,R)$ be all vertices directly inserted into interval $(L,R)$.

Define solve(L,R) to return:

• size: how many real vertices lie inside interval $(L,R)$;
• ways: how many valid orders those vertices have, assuming $L$ and $R$ are fixed boundaries.

Now look at one direct vertex $x \in B(L,R)$.

Everything in interval $(L,x)$ must be before $x$. Everything in interval $(x,R)$ must be after $x$. Therefore $x$ forms one component:

$\text{solve}(L,x),\quad x,\quad \text{solve}(x,R).$

Its size is

$s_x = size(L,x)+1+size(x,R),$

and its internal number of ways is

$ways(L,x) \cdot ways(x,R).$

Different direct vertices inside the same interval are incomparable. If two such vertices were ancestor and descendant in the original tree, then the ancestor would sit between $L$ and $R$ and the descendant could not have the same direct interval. So these components are independent chunks that can be interleaved arbitrarily.

If we already placed components of total size $S$, and the next component has size $s$, we choose its positions in

$C(S+s,s)$

ways. Multiply that by the component's internal ways.

So the transition is:

ways = 1, total = 0
for x in B(L,R):
    left = solve(L,x)
    right = solve(x,R)
    s = left.size + 1 + right.size
    w = left.ways * right.ways
    ways *= w * C(total+s, s)
    total += s

The answer is solve(0,n+1).ways, where $0$ and $n+1$ are the two sentinels.

Complexity

Building intervals with the DFS costs $O(n^2)$ because of vector insert/erase on root-to-node chains. The interval DP itself touches each vertex as a direct interval member once, so it is $O(n)$ plus hash-map overhead. Precompute factorials and inverse factorials for combinations.

Total complexity per all tests is $O((\sum n)^2)$ in the worst chain case, which is fine for $\sum n \le 5000$.