 # 50 points for Counting Graphs without DFS

for first subtask :
fact 1 : the graph should be tree
cnt_x is number of x's in a
fact 2 : if cnt_i > 0 so for every j<i the Condition should held : cnt_j > 0
fact 3 : every i should connect to one with depth i - 1 so number of different ways is multiple of all {cnt_{i-1}}^{cnt_i} for 2 <= i <= n - 1

submisson

note : tav function is binary pow

2 Likes

My solution is just count frequency of nodes which are at level i , initially mp = 1 , now
ans is

ans = mp[ 0 ]mp[ 1 ] * mp[ 1 ]mp[ 2 ] * mp[ 2 ]mp[ 3 ] . . . .

2 Likes

The second subtask is just a piece of cake if you have solved first subtask.

Can you please tell me how to solve it? @meet2mky

1 Like

How?

1 Like

See my solution: Link

2 Likes

Can You say the answer for second subtask ???
Thanks @meet2mky

1 Like

Solving for the first subtask was fairly straight-forward. It infact took me less time than ARRGAME to get it.

All you need is than any edge cannot connect two nodes of distance greater than 2. Then just use nCr.

@amir_reza How to prove fact3 ?

as they are n - 1 edges so every node with depth x - 1 is father of node with depth x so for every node with depth x there is cnt_{x - 1} chooses so the answer will be
multiple of all {cnt_{i-1}}^{cnt_i}

1 Like

can you take an example of simple tree and elaborate ? Edit : @amir_reza i understood. Thanks  Additional edges can only be connected between nodes of same height.
max_pos_edges after tree construction would be sum of cnti choose 2 for each i. where cnti is the number of nodes at height i. Now multiply answer by max_pos_edges choose (m - (n-1)).

The solution for 100 points is very easy once you get this part right. Need to multiply this with just one nCr term ,

Editorial for 100 points :- https://discuss.codechef.com/t/counting-graph-editorial-100-points/76382/4