根付き木の頂点に順列を割り当てて，親の頂点の値が子よりも小さくなるようにする問題です．

\(P_U<P_V\) の条件がなければ，木の各頂点について \(1/(\)部分木サイズ\()\) をかけた積を求めればよいです．

\(P_U<P_V\) の条件を考えると，制約が木でなくなってしまうのが問題です．

\(V\) の親を \(W\) とおくことにします． \(V\) を部分木ごと \(W\) から切り離し，\(U\) の子としてつけなおします． こうして得られた木で制約を満たす順列を数えてみます． \(P_U<P_V\) の条件が必ず満たされている代わりに，\(P_W<P_V\) の条件が外れています．

そこで，この新しい木で \(P_V<P_W\) という制約を追加した場合の問題を考え，その答えを \((-1)\) 倍した値を足すことにします．

こうして得られた新しい問題は，元の問題と同じ構造をしています． つまり，\(W\) をさらにその親から切り離して \(V\) の子にして…と繰り返すことで，問題をどんどん別の問題に帰着していくことができます．

追加される制約を \(P_x<P_y\) と表すことにすると，\(LCA(x,y)\) と \(y\) の距離が \(1\) ずつ減るので，この帰着は \(O(N)\) 回で終了します．

後は木の問題を解くだけです． 条件を満たす順列の個数を律義に求めてもよいですが，最終的に求めたい確率の分子と分母で共通する項を無視すると実装が楽です． 結局，\(x,y\) パス上の各頂点の部分木サイズの総積を求めればよく，これは \(O(N)\) で行えます．

よって全体で \(O(N^2)\) でこの問題は解けます．

なお，時間制限を長めに設定しているので，\(O(N^2)\) 回 mod 逆元を求めるような解法も（定数倍が悪くなければ）通ります．

解答例

おまけ：\(O(N\log^2N)\) で解けます．