kmjp's blog

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

Codeforces #332 Div2 E. Sandy and Nuts

Codeforces

勉強になる木DPだった。
http://codeforces.com/contest/599/problem/E

問題

1～Nの頂点からなり、1番の頂点を根とする根付木を考える。

木を構成する(N-1)本の辺のうち、M本分の頂点対(U[i],V[i])が指定されている。
また、(A[i],B[i],C[i])の3値からなるQ個のクエリが与えられる。
各クエリは、頂点がLCA(A[i],B[i])=C[i]であることを示す。

1～Nの頂点からなり、1番の頂点を根とする根付木のうち、指定されたM本の辺をもち、かつQ個のクエリの条件を満たすものの数を求めよ。

解法

まず辺とクエリ指定は無視して、根付き木の数え上げを考える。
x番の頂点を根とし、直接の子頂点の最大番号がy以下で、bitmaskに示す点から構成される根付き木の数をF(x,y,bitmask)とする。

root番の頂点を根とし、子頂点がchild未満であるような木に、別の頂点childを根とする木をroot直下に連結すると考える。
bitmaskのsubmaskを考え、rootmask | childmask = bitmaskとなるrootmask/childmaskに対し、
F(root,child,bitmask) += F(root,child,rootmask) * F(child,N,childmask)
が成り立つので、これを計算していけば良い。

あとは、root/child/rootmask/childmaskに対し、辺の指定とクエリに沿わないものがある場合は加算をやめる。

まず辺指定について、U[i],V[i]がそれぞれrootmask/childmaskの片方ずつに属していて、かつそれぞれがroot/childでない場合、今後U[i]とV[i]の間に辺が張られる見込みはないので加算をやめる。

次にクエリ指定について、以下の何れかの場合はLCA(A[i],B[i])がC[i]になり得ないので加算をやめる。

  • rootmask側にC[i]がすでに含まれているのに、そこにA[i],B[i]が含まれていない。
  • submask側も同様
  • 元のbitmask中にA[i],B[i]も含まれているのにC[i]が含まれない
int N,M,Q;
int mat[15][15];
ll dp[15][15][1<<13];
int U[30],V[30];
int A[101],B[101],C[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	FOR(i,M) cin>>U[i]>>V[i], U[i]--, V[i]--;
	FOR(i,Q) {
		cin>>A[i]>>B[i]>>C[i], A[i]--, B[i]--, C[i]--;
		if(A[i]==B[i]) {
			if(A[i]!=C[i]) return _P("0\n");
			i--;
			Q--;
		}
	}
	
	for(int mask=1;mask<1<<N;mask++) {
		FOR(i,N) if(mask & (1<<i)) {
			if(__builtin_popcount(mask)==1) {
				dp[i][0][mask] = 1;
			}
			else {
				for(int root=mask; root>0; root=(root-1)&mask) if(root&(1<<i)) {
					int add = mask ^ root;
					
					FOR(j,N) if(add&(1<<j)) {
						int ng=0;
						FOR(x,M) {
							if((root&(1<<U[x])) && (add&(1<<V[x])) && (i!=U[x] || j!=V[x])) break;
							if((root&(1<<V[x])) && (add&(1<<U[x])) && (i!=V[x] || j!=U[x])) break;
						}
						if(x<M) continue;
						FOR(x,Q) if(i!=C[x]) {
							if(root & (1<<C[x])) {
								if(!(root&(1<<A[x])) || !(root&(1<<B[x]))) break;
							}
							else if(add & (1<<C[x])) {
								if(!(add&(1<<A[x])) || !(add&(1<<B[x]))) break;
							}
							else {
								if((mask&(1<<A[x])) && (mask&(1<<B[x]))) break;
							}
						}
						
						if(x==Q) dp[i][j][mask] += dp[i][j][root]*dp[j][N][add];
					}
				}
			}
			FOR(j,N) dp[i][j+1][mask] += dp[i][j][mask];
		}
	}
	
	cout<<dp[0][N][(1<<N)-1]<<endl;
	
}

まとめ

辺やクエリの条件をどうbit演算でこなすか、また数え上げの重複を防ぐのに若干苦労。