EXPTREE - Editorial

Forget formal proof. Right at the beginning of the paper there is formula for the number of nodes with d children.

Can anybody please elaborate on the observation 2 part please -“Let’s consider all different (n-1) ordered trees, and think about applying this operation. Choosing an arbitrary node of a tree and linking it to a single child (nth node) and removing all edges between our chosen node and its children, then linking them to our new node. So our new node would serve as a single child of the chosen one”
How to perform this operation?

“Observe that each node in a tree consisting of n nodes and having only one child can be formed by applying this operation to only one tree of (n-1) nodes. It’s exactly the same as choosing an opened bracket and its corresponding closing bracket in a simple balanced bracket sequence framing the subexpression between by a pair of brackets (our new node).”

Would you mind adding in a pictorial representation to describe how the operation is done?

1 Like

What difference does it make if I write 2*(n)%MOD and (n+n)%MOD?

Can someone explain in detail more about what ordered trees mean in this context? I have checked on various site - stackoverflow etc . but couldnt understand much…
Thanks in advance.

After some hours of hard thinking, I came up with this explanation/proof for the calculation of p. Hope it is useful and to get feedback in case I’m mistaken.


We want to count the number of vertices with one child in all trees of n + 1 vertices (n edges). Let’s call this number p’.

Imagine to lay out all the C_n trees and label each tree’s vertices from 0 to n, top-to-bottom, left-to-right (the root is always 0).

To find p’, you could fix a tree, count the number of vertices with one child in this tree, and then sum over all the trees. This doesn’t lead to an easy closed formula.

Instead, fix a vertex v in [1…n] and count how many trees, among the C_n, are such that parent[v] has only one child v. Summing over all v’s will give us p’.

For each v, removing (parent[v], v) from the tree by the operation explained above, gives us a n-vertice tree. There are exactly C_{n-1} such trees and they must all appear in our original layout (of C_n trees).

Furthermore, there is no double-counting: otherwise there would be v1, v2 in [1…n] from trees T1, T2 resp., such that removing (parent[v1], v1) and (parent[v2], v2) leads to the same tree, except for the labels. This means T1=T2 would appear twice in out original layout, which is impossible by construction.

There are n vertices, each associated with C_{n-1} trees, therefore p’ = n * C_{n-1}. For p, just let n = k - 1 and substitute.

1 Like

I have explained my solution here Though it is very long I have made an attempt to explain everything.

In the mentioned paper:

The number of nodes of degree, d in all the trees in T,

  1. = the number of occurrences of d in all the sequences in I,
  2. = the number of occurrences of runs of exactly d(‘s (or equivalently
    d)‘s) in all the expressions in P(Parenthesis representation).

How can the 2nd statement be justified, say suppose d=1, then according to 2nd statement, number of nodes of degree 1 would be all ‘(’ brackets and that would n, which doesn’t seem to be true.

Am I missing something which is not so obvious?

You mean gcd() of any two numbers in this case will definitely 1?

True because while applying inverse condition is that a and m should be coprime ba-1(inverse)%m and if a is not a multiple of m multiples of a also cannot be multiples of m and hence they are coprime too.

@bansal1232 No gcd in this case will not at all be 1 (in all cases may be in some) but the thing is you don’t need them to be 1 because
8/2%5=4 and 4/1%5=4.

1 Like

5^-1 gives 400000003, multiply it by 6 and then take mod. You’ll get the desired op.

you can find inverse using fermat’s theorem in logN time.

t test cases. so t*log 10^7 gives time out. O(n) compute (ony one time for n=2 to n=1000),store and then using it is more faster.

It didnt gave TLE to me when i did the same @rj25 . In fact, code passed well within the time limit.

@vijju123 can you give link to your solution ?CodeChef: Practical coding for everyone My solution using that approach only gave me 10 points. But @vijju I think my final approach is much faster than O(log n) one.

https://www.codechef.com/viewsolution/14495303

Here @rj25

Your solution is much simpler than mine. I have complicated everything by not taking n%m right from start.

1 Like

I have added an extra small explanation

I have added an extra small explanation