Codeforces #926 : Div2 E. Sasha and the Happy Tree Cutting

どうにか全完。
https://codeforces.com/contest/1929/problem/E

問題

N点の木を成す無向グラフと、K個のパスが与えられる。
木のうち何辺かに色を塗り、各パスにおいて1個以上色を塗った辺があるようにしたい。
最少何辺色を塗ればよいか。

解法

まず、各辺を塗ることでどのパスをカバーできるか列挙する。
あとはBitDPの要領で、パスの部分集合をカバーするのに必要な辺の数の最小値を求めて行けばよい。
愚直にやるとTLEするので、適度に枝刈りを入れる。

int T,N,K;
int A[20],B[20];
vector<int> E[101010];
int M[202020];
int P[202020];
int cost[1<<20];

int dfs(int cur,int pre) {
	if(cur) P[cur]=pre;
	FORR(e,E[cur]) if(e!=pre) M[cur]^=dfs(e,cur);
	return M[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			E[i].clear();
			M[i]=0;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		cin>>K;
		FOR(i,K) {
			cin>>x>>y;
			M[x-1]|=1<<i;
			M[y-1]|=1<<i;
		}
		int mask;
		FOR(mask,1<<K) cost[mask]=1<<20;
		cost[0]=0;
		dfs(0,0);
		vector<int> cand;
		FOR(i,N) if(i) {
			cost[M[i]]=1;
			cand.push_back(M[i]);
		}
		sort(ALL(cand));
		cand.erase(unique(ALL(cand)),cand.end());
		
		FOR(i,K) FOR(mask,1<<K) if(mask&(1<<i)) chmin(cost[mask^(1<<i)],cost[mask]);
		FOR(mask,1<<K) if(cost[mask]!=1) {
			int ma=0;
			FOR(i,K) if(mask&(1<<i)) ma=i;
			
			x=1<<(__builtin_popcount(mask)-1);
			
			if(x<=cand.size()) {
				for(int sm=mask^(1<<ma);sm>0;sm=(sm-1)&mask) {
					chmin(cost[mask],cost[sm]+cost[mask^sm]);
				}
			}
			else {
				FORR(c,cand) {
					chmin(cost[mask],cost[mask^(mask&c)]+1);
				}
			}
		}
		cout<<cost[(1<<K)-1]<<endl;
		
	}
		
}

まとめ

TLE回避に手間取った。