yukicoder : No.758 VVVVV

知識ゲー…？
https://yukicoder.me/problems/no/758

問題

N頂点の根付きの順序木が与えられる。
この木をDFSでたどる場合、親から子に下がる処理をA、子から親に上がる処理をBとし、処理順に並べた文字列を考える。
A→BまたはB→Aの順に並ぶ位置がM箇所あったとする。

ラベルのないN頂点の根付き木のうち、上記処理を行うと同じくM箇所となるようなものは何通りか。

解法

Mは、結局木における葉の数で決まる。
葉の数だけA→Bの順が登場するし、(葉の数-1)の数だけB→Aの順が現れる。

とすると、N頂点(N-1)辺の順序木のうち葉がM個の物を列挙する問題となる。
関連するキーワードで調べるとこんな解説記事(PDF)が見つかるので、そこにある式を流用しよう。
http://www.nakano-lab.cs.gunma-u.ac.jp/Papers/080110.pdf

int N;
vector<int> E[101010];
int ret=0;

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void dfs(int cur,int pre) {
	if((pre==-1 && E[cur].empty()) || (pre>=0 && E[cur].size()==1)) ret++;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
}


ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	if(N==1) return _P("1\n");
	
	dfs(0,-1);
	
	cout<<comb(N-1,ret-1)*comb(N-2,ret-1)%mo*modpow(ret)%mo<<endl;
}

まとめ

ゲームVVVVVはやったことないこともあり、最初タイトル由来は東亜プランのV・V？とも思ったけど考えたらV・Vもやったことなかった。