i didn’t even understand the tutorial
this is one quote good submission maybe it will help.
plz explain it anyone!1
You can notice that the number of ways to permute the values doesn’t depend on the actual values itself, since the neccesary condition only depends on the relative values.
So let dp_i denote the number of ways to permute values on the subtree of i and S_i denote the size of the subtree at i.
Now to calculate dp_i, we can notice that the smallest value can only be on i. Then we have to split the rest of the values and give them to the children of i.
The number of ways to split them is (S_i -1)! \prod \frac{1}{S_c!}.
Each subtree will have dp_c arrangements internally, so the final dp relation is
dp_i = (S_i -1)! \prod \frac{dp_c}{S_c!}.
This can be calculated by a simple DFS.
2 Likes