Hello community,

While solving the problem Tree Array from recent Codeforces Round 728 Div2(https://codeforces.net/contest/1541/problem/D)- I came up with the following solution which is failing on example test case 3.

The steps that I followed. 1) For each node r as root, the expected value of inversions can be expressed as p/q so the expected number of inversions considering all the n nodes as root r,one at a time, should be (p_1/q_1 + p_2/q_2 + p_3/q_3+ ...p_n/q_n) mod m=((p_1/q_1)%m +(p_2/q_2)%m + ...(p_n/q_n)%m)%m.

2) Now I observe that if I fix a node r as root, then for some pairs of elements a constant order of appearance is maintained across all the possible arrays that can be made by following the mentioned process and for some pairs of elements , their order of appearance across all the possible arrays is not fixed. Specifically, if we consider a pair of nodes (a,b) then a will always appear before b if b is in the subtree of a. And if the value of node a is greater than that of node b, then this inversion shall exist across all the possible arrays that can be made considering the node r as root as mentioned earlier. For other pairs, where one node is not in the subtree of other, in some cases, they will appear as inversions and in some cases, they will not. So ,for a particular node r as root, I count the number of pairs of elements which will always give an inversion across all the possible array combinations and mark that count as 'constant'. And I also count the number of pairs of nodes, for which no such fixed order is maintained and call that count as 'variable'. Suppose the value of 'variable' is x. We can visualize it as : there are x bits where each bit denotes a particular pair whose order is not fixed. So if the bit is set, it means that pair has occurred as an inversion otherwise not. If we consider all the values from 0 to ((2^x)-1), then for each such value, the number of set bits in that value + 'constant' will give us inversion count of one of the arrays that is possible if we take the node r as root as mentioned above and follow the process as mentioned in the question. So, we can easily obtain , for a particular node r, what are the possible inversion counts that we can get from all arrays formed by following that process as mentioned in the question and also how many times each such inversion value occurs while we are considering node r as root. Let's take the case of example 3 illustrated in the problem : Suppose if we fix 4 as root, then upon performing dfs we get 4,1,2,5,3. Now for each of the pairs (4,1),(4,2),(4,3),(4,5),(1,2),(1,3),(1,5),(2,5) the relative order of the first and second elements in the pair will always be maintained across all arrays we can get by following the process for 4 as root node, as we shall always the enter the node containing the first value of the pair before the node containing the other value because a node cannot be marked unless its parent has already been marked. Therefore the 'constant' has the value 3 here as among all the pairs mentioned earlier, in only the first 3 pairs do we have an inversion. For each of the pairs (2,3),(5,3), their relative order of appearance will not be fixed as for a particular pair, one of the nodes is not in the subtree of the other. So , here, the value of 'variable' is 2. Now, if we consider each of the values from 0 to 3 i.e (2^2-1), then 'constant' + number of set bits will give us the following : 3+0(when none of the bits is set),3+1(when one bit is set),3+2(when two bits are set) gives us 3,4,5 respectively which are all the possible values that inversion count can have when we consider all possible arrays for root 4 as node. The frequency of each of these values can be counted by finding how many times each count of set bits appears across all the values. So for the above example, from 0 to 4, two values has set bit count 1(2C1), one value has set bit count 2(2C2) and one value has set bit count 0(2C0). So 4 occurs twice as inversion count,3 occurs once as inversion count and 5 occurs once as inversion count. Therefore for node 4 as root node, we have p=4*2+3*1+5*1 and q=1+2+1=4. Therefore expected value of inversions for node 4 as root node will be p/q i.e 16/4=4. Similarly ,we can do for other nodes as roots.

Unfortunately, this solution is failing on the same test case with which I illustrated above. Can anyone of you kindly find any fallacy in this approach? It would be really of great help. The editorial explanation seems tough to understand and my logic feels very intuitive for me although the answer is coming wrong.