kmjp's blog

競技プログラミング参加記です

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)選ぶので、その順列を考えるとP_{AB}=P_{BC} \times P_{BD} \times P_{BE} \times {}_{N_{AB}} C_{N_{BC}} \times {}_{N_{AB} - N_{BC}} C_{N_{BD}}とかける。

NとPを全部求めたら、あとは最初の辺をA-Bで選択した場合、その組み合わせは P_{AB} \times P_{BA} \times {}_{R-1} C_{N_{AB}}となるのでそれを各辺ごとに足しこんでいけばよい。

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問題で苦しんだ成果が出ているようだ。