TopCoder SRM 644 Div2 Hard TreeCutting

枝刈りを頑張る必要があるか迷ったが、特に必要なかった。

問題

N頂点からなる木を成すグラフが与えられる。
一部の頂点には数字が振られている。

以下の条件を満たすよう、一部の辺を切断して森を作ることは可能か答えよ。

• 各木において、数字が振られている頂点は1つである。
• 各木において、上記頂点の数値は木に含まれる頂点数に等しい。

解法

木の各辺を探索し、各辺を切断して２つの木を作ったとき、それぞれ頂点中の数値の和が頂点数に一致するなら、そこは切断する。
後はこの処理を再帰的に行うだけ。

木を切断した２つの木がまた条件を満たすなら、そこは切断しなければならない辺となる。
そのため各辺を切断するかしないか迷うケースは存在せず、メモ化再帰しなくても状態数が発散せず時間は間に合う。

int mat[51][51];

class TreeCutting {
	public:
	int N;
	vector<int> P,num;
	bool ok(ll mask,int st) {
		int no=0;
		int i,j,t=0,nv=__builtin_popcountll(mask);
		int V[51],nev=0;
		
		FOR(i,N) if(mask&(1LL<<i)) {
			V[nev++]=i;
			if(num[i]>=0) t+=num[i], no++;
		}
		if(t!=nv) return false;
		if(no==1) return true;
		
		for(i=st;i<N-1;i++) {
			if((mask&(1LL<<(i+1)))==0) continue;
			if((mask&(1LL<<P[i]))==0) continue;
			
			ll mask2=0,mask3=0,n2=0,n2o=0,n3=0,n3o=0;
			FOR(j,nev) {
				if(mat[V[j]][i+1]<mat[V[j]][P[i]]) {
					mask2 |= 1LL<<V[j], n2++;
					if(num[V[j]]>=0) n2o++, n2-=num[V[j]];
				}
				else {
					mask3 |= 1LL<<V[j], n3++;
					if(num[V[j]]>=0) n3o++, n3-=num[V[j]];
				}
			}
			if(n2o<1 || n3o<1 || n2!=0 || n3!=0) continue;
			return ok(mask3,i+1) && ok(mask2,i+1);
		}
		return false;
	}
	
	string can(vector <int> par, vector <int> num) {
		int i,t=0,x,y;
		P=par;
		this->num=num;
		//FOR(i,65) M[i].clear();
		N=par.size()+1;
		
		FOR(x,N) FOR(y,N) mat[x][y]=1000;
		FOR(i,N-1) mat[par[i]][i+1]=mat[i+1][par[i]]=1;
		FOR(x,N) mat[x][x]=0;
		FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		if(ok((1LL<<N)-1,0)) return "POSSIBLE";
		return "IMPOSSIBLE";
	}
}

まとめ

若干実装は面倒なものの、アイデア自体はDiv2Hardにしても簡単な気がする。