P9536 [YsOI2023] Prüfer Sequence

A counting problem for Ysuperman’s template testing. As everyone knows, the Prüfer sequence has almost never appeared in official contests, so it needs to appear in a Luogu Monthly Contest.

As everyone knows, a labeled unrooted tree with $n$ nodes corresponds one-to-one with its Prüfer sequence. If you do not know what a Prüfer sequence is, you can refer to the explanation in the Hint section below. Now you are given a positive integer sequence $a$ of length $m$, where $a_i\in[1,n]$. Uniformly at random, choose a subsequence of this sequence with length $n-2$ (as long as the chosen indices are different, the two subsequences are considered different) and use it as a Prüfer sequence to construct a tree $T$. For all $1\le i

The first line contains two positive integers $n,m$. The second line contains $m$ integers representing the sequence $a$, and it is guaranteed that $1\le a_i\le n$.

Output $n-1$ non-negative integers. The $i$-th integer denotes the expected value of $\mathrm{dist}(i,n)$.

#### Explanation of the Prüfer sequence For a given unrooted labeled tree, the construction process of its Prüfer sequence is as follows: each time, select the leaf node with the smallest label and delete it, then record in the sequence the node it is connected to. Repeat this $n-2$ times; after that, only two nodes remain, and the recorded sequence is the Prüfer sequence of this unrooted labeled tree. We can prove that an unrooted labeled tree with more than $1$ node corresponds one-to-one with a Prüfer sequence, and that any Prüfer sequence of length $n-2$ with each number being an integer in $[1,n]$ has a unique corresponding tree. Similarly, we can also restore a tree from a Prüfer sequence. For more detailed content about the Prüfer sequence, you can refer to [the description of the Prüfer sequence on OI-wiki](https://oi-wiki.org/graph/prufer/). #### Sample 1 explanation There are three equally likely subsequences to choose from: $2,4$, $2,3$, $4,3$. 1. The tree corresponding to $2,4$ is a chain $1-2-4-3$, and the distances from $1,2,3$ to $4$ are $2,1,1$, respectively. 2. The tree corresponding to $2,3$ is a chain $1-2-3-4$, and the distances from $1,2,3$ to $4$ are $3,2,1$, respectively. 3. The tree corresponding to $4,3$ is a chain $1-4-3-2$, and the distances from $1,2,3$ to $4$ are $1,2,1$, respectively. Therefore, the expected value of $\mathrm{dist}(1,4)$ is $(2+3+1)/3=2$, the expected value of $\mathrm{dist}(2,4)$ is $(1+2+2)/3=5/3\equiv 666666673\pmod{10^9+7}$, and the expected value of $\mathrm{dist}(3,4)$ is $(1+1+1)/3=1$. #### Sample 2 explanation There is only one possible subsequence $4,6,5,2$, and the corresponding tree is a chain $1-4-5-2-6-3$. The distances from $1,2,3,4,5$ to $6$ are $4,1,1,3,2$ in order, which is the answer. #### Constraints This problem has a total of $20$ test points: |Test Point ID|$n$|$m$| |:-:|:-:|:-:| |$1$|$=4$|$=6$| |$2$|$=8$|$=15$| |$3$|$=10$|$=20$| |$4$|$=10$|$=50$| |$5$|$=10$|$=200$| |$6$|$=10$|$=1000$| |$7$|$=10$|$=1750$| |$8$|$=10$|$=2500$| |$9$|$=11$|$=500$| |$10$|$=11$|$=1000$| |$11$|$=12$|$=250$| |$12$|$=12$|$=375$| |$13$|$=12$|$=400$| |$14$|$=13$|$=80$| |$15$|$=13$|$=120$| |$16$|$=13$|$=160$| |$17$|$=13$|$=200$| |$18$|$=14$|$=60$| |$19$|$=14$|$=90$| |$20$|$=15$|$=40$| In addition, for all testdata, it is guaranteed that $1\le a_i\le n$. **Please note that the memory limit for the first $19$ test points is $512\rm{MB}$, and the memory limit for the last test point is $150\rm{MB}$.** Translated by ChatGPT 5