18948번 - Tree Average Weight 다국어

Consider a labeled tree with its vertices numbered from $1$ to $n$.

Let us define the weight of the tree as the sum over all edges $uv$ of values $u \cdot \mathrm{sz}_{uv}(u) + v \cdot \mathrm{sz}_{vu}(v)$, where $\mathrm{sz}_{vu}(v)$ is the size of subtree containing $v$ after deleting edge $(vu)$.

You are given an array $a$ of size $n$. Elements of the array are either integers between $1$ and $n-1$ (inclusive), or equal to $-1$. The $v$-th element corresponds to the degree of vertex $v$. We say that a tree with $n$ vertices is good if for all $v$ such that $a_{v} \ne -1$, it is true that the degree of $v$ equals to $a_{v}$. In other words, if $a_{v} = -1$, then $v$ can have any degree, and otherwise, its degree is fixed and equal to $a_{v}$.

Let us choose one of the good trees randomly with equal probability. Denote the expected value of the weight of this tree as $E$. Find the integer part of $E$.

The first line of input contains an integer $n$: the size of the tree ($2 \le n \le 10^{6}$).

The second line of input contains an array of size $n$. Each element of the array is either an integer between $1$ and $n-1$ (fixed degree), or equal to $-1$ (arbitrary degree). It is guaranteed that the sum of absolute values of elements is not greater than $2n-2$.

Print the integer part of $E$.