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

note : tav function is binary pow