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 · szuv(u) + v · szvu(v), where szvu(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 av ≠ −1, it is true that the degree of v equals to av. In other words, if av = −1, then v can have any degree, and otherwise, its degree is fixed and equal to av.
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 ≤ n ≤ 106).
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.
1 -1 -1 -1 -1
-1 -1 -1 -1 1
1 1 1 3
1 1 2 2
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest