I don't really get it, do you think DEF was super easy or completely unsolvable?

We maximize the number of nodes we have at each level. First, note that there can only be as many nodes at any level as there are leaves at or below that level in the tree. Second, note that there can only be twice as many nodes at any level as there were non-leaf nodes at the previous level. At each level, we add the minimum of these two values to the answer. We print -1 if any level has fewer nodes than it must have leaves.

I probably won't be able to go into specifics, but a general outline of my solution is below.

First, we consider the conditions required for a sequence to be good. It turns out that the following condition is both necessary and sufficient: for all $$$i < j$$$, if $$$A[i]$$$ contains a $$$1$$$ as its $$$k$$$'th least significant bit and $$$A[j]$$$ contains a $$$0$$$ as its $$$k$$$'th least significant bit, then $$$A[i]$$$ and $$$A[j]$$$ must be equal in the $$$1$$$st through $$$k-1$$$'th least significant bits.

We can extend this to note that for any bit $$$k$$$, all elements ranging from the first one with a $$$1$$$ in position $$$k$$$ to the last one with a $$$0$$$ in position $$$k$$$ must be equivalent in all bits $$$1$$$ through $$$k-1$$$.

To count sequences satisfying this condition, we do DP, where $$$dp[i][j]$$$ is the number of ways to set the $$$i$$$ most significant bits such that there are $$$j$$$ elements not forced to be equivalent. Then, we can compute the number of ways to transition from an array with $$$j$$$ elements to one with $$$k$$$ elements, for each $$$k$$$, by computing the number of ways to assign 0s and 1s to bit $$$i$$$ such that, when we merge every element from the first $$$1$$$ to the last $$$0$$$, we're left with exactly $$$k$$$ elements. This takes $$$O(nm^2)$$$ time if implemented naively, but using prefix sums can speed it up to $$$O(nm)$$$.

You do know the third sample is failing, right?

The crucial observation is that in each component there can be only one vertex with $$$-1$$$. Each new edge decreases the number of components by one, except for the case when it forms a cycle. So we should count the number of cycles — it's dp in $$$O(n^2)$$$.

When all $$$-1$$$ are replaced, we get a so-called function graph, except we don't care about directions. The number of edges is $$$N$$$ — number of cycles. For each possible cycle, we want to find the number of assignments of $$$-1$$$ that result in it.

Let $$$C$$$ be a component in the input graph that contains a cycle. This cycle will be there all the time, so we subtract $$$(N-1)^K$$$ for each of them. From now on, we can ignore them.

When can a cycle that didn't exist be created? Consider trees rooted at vertices $$$i$$$ with $$$P_i=-1$$$; there are $$$K$$$ such trees with sizes $$$S_1, S_2, \ldots, S_K$$$. A cycle will visit some subset of these trees in some order. If it visits a subset $$$X$$$, there are $$$(|X|-1)!$$$ orderings and the number of assignments that result in such a cycle is $$$\prod_{j \in X} S_j \cdot (N-1)^{K-|X|}$$$ if $$$|X| \gt 1$$$, or $$$(S_j-1)(N-1)^{K-1}$$$ if $$$X = {j}$$$. Proof: just fix a cyclic sequence of trees that go in the cycle and for each tree, make an edge from its root to a vertex from the next tree in the sequence; the remaining $$$K-j$$$ edges can be assigned arbitrarily.

We want to get the sum $$$c_k$$$ of $$$\prod_{j \in X} S_j$$$ over all subsets with size $$$k$$$, for each $$$k \gt 1$$$; then, the answer can be computed using the formulas above. This, in fact, is just polynomial multiplication — $$$c_k$$$ is the coefficient of $$$K-k$$$ in $$$\prod_{j=1}^K (x+S_j)$$$. This can be computed most easily using divide&conquer with Karatsuba's algorithm in $$$O(N^{\log_2 3})$$$ (the log-factor from d&c is eaten by Karatsuba), or with FFT in doubles in $$$O(N \log^2 N)$$$.

after 4-5 days at https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0

Thank you for good contest

The model solution is of O(N^2) time.

_t can exceed long long range https://ideone.com/WCUZ3U