Typical DP Contest : N - 木

これも自力で迷わず解けた。うーん、TDPCの5ptエリアは自分の解けない問題が前半に来ていたな。
後半の問題もちゃんと見ればよかった。
http://tdpc.contest.atcoder.jp/tasks/tdpc_tree

問題

N点からなるグラフにおいて、辺同士が連結した状態を保って最終的に与えられた木を作る。
作り方の手順は何通りあるか。

解法

辺A-Bに対しB側にある辺の数と辺をすべて埋める手順をN[A][B]、P[A][B]とする。
まずこのNとPをDPで埋めていく。

たとえばBはA,C,D,Eに辺を伸ばすとすると、辺A-B以外の辺をたどりN[B][C]、N[B][D]、N[B][E]、P[B][C]、P[B][D]、P[B][E]を再帰的に計算できる。
N[A][B]は(Bから張る辺の数-1)+N[B][C]+N[B][D]+N[B][E]とかける。(A-Bを無視するので1引く)
P[A][B]はCの先にある辺を(N[B][C]+1)回、Dの先にある辺を(N[B][D]+1)、Eの先にある辺を(N[B][E]+1)選ぶので、その順列を考えるととかける。

NとPを全部求めたら、あとは最初の辺をA-Bで選択した場合、その組み合わせはとなるのでそれを各辺ごとに足しこんでいけばよい。

int N;
vector<int> E[1001];
ll mo=1000000007;
ll pat[1001][1001];
ll num[1001][1001];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	return C_[P_][Q_];
}

void dodo(int pre,int cur) {
	if(pat[pre][cur]==-1) {
		pat[pre][cur] = 1;
		num[pre][cur] = E[cur].size()-1;
		int x,tar;
		FOR(x,E[cur].size()) {
			tar = E[cur][x];
			if(pre==tar) continue;
			dodo(cur,tar);
			pat[pre][cur] = (pat[pre][cur] * pat[cur][tar]) % mo;
			num[pre][cur] += num[cur][tar];
		}
		int tot=num[pre][cur];
		FOR(x,E[cur].size()) {
			tar = E[cur][x];
			if(pre==tar) continue;
			pat[pre][cur] = (pat[pre][cur] * comb(tot,num[cur][tar]+1)) % mo;
			tot -= num[cur][tar]+1;
		}
	}
}

void solve() {
	int f,r,i,j,k,l, x,y,z,mask=0;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(x,N) FOR(y,N) pat[x][y]=num[x][y]=-1;
	FOR(x,N) FOR(y,E[x].size()) dodo(x,E[x][y]);
	
	ll tot=0;
	FOR(x,N) FOR(y,E[x].size()) {
		z = E[x][y];
		if(x<z) tot = (tot + ((pat[x][z]*pat[z][x])%mo)*comb(num[x][z]+num[z][x],num[x][z])) % mo;
	}
	
	return _P("%lld\n",tot);
}

まとめ

以前Codeforces #178 Div2. E. Shaass the Great - kmjp's blogで木のDFS問題で苦しんだ成果が出ているようだ。