New Year Contest 2015 : E - ひも

これは知識ゲーな部分もあるかな…。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_5

問題

N個のラベル付き頂点を(N-1)辺で連結させ、木を作る。
各頂点につながる辺の数はA[i]である。

木に組み合わせは何通りあるか。

解法

まず前提として、辺が(N-1)本なのでA[i]の総和は2*(N-1)である。
後は以下にページにある公式を使うだけで解ける。
Prüfer sequence - Wikipedia

他にも、先にA[i]==3の点とA[i]==1の点の組み合わせを求め、後はA[i]==2の点を辺の途中に挿入していくDPでも良い。

int N;
int A[101000],R[4];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	if(accumulate(A,A+N,0)!=2*(N-1)) return _P("0\n");
	
	R[1]=R[2]=1, R[3]=(mo+1)/2;
	
	ll ret=1;
	FOR(i,N-2) ret = ret*(i+1)%mo;
	FOR(i,N) ret = ret*R[A[i]]%mo;
	cout<<ret<<endl;
}

まとめ

DP解、うまく重複ケースが処理できず本番解ききれなかった。