yukicoder : No.2980 Planar Tree 2

これはすんなり。
https://yukicoder.me/problems/no/2980

問題

N頂点の木が与えられる。
今円周上にランダムに1～N番の点を配置し、元の木のように頂点間に辺を張るとき、辺同士が端点以外で交差しない確率を求めよ。

解法

全点の並び順は(N-1)!通り。
各点を根とした場合を考えると、各点のsubtree同士が交差しないためには、円周上でそのsubtree内の頂点同士が連続して配置されればよい。
よって点vの次数をE(v)とすると、解は

int N;
vector<int> E[202020];
const ll mo=998244353;

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll ret;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	ll ret=1;
	FOR(i,N) ret=ret*fact[E[i].size()]%mo;
	
	ret=ret*factr[N-1]%mo;
	cout<<ret<<endl;
	
	
}

まとめ

想定解法と違った…。