Codeforces #875 : Div1 D. Mex Tree

本番中のAC数に対しupsolveが妙に多いな。
https://codeforces.com/contest/1830/problem/D

問題

木を成すグラフが与えられる。
各点に非負整数を設定したとき、頂点対を両端とするパスに対し、パス上の頂点の設定値のMEX値の総和を最大化せよ。

解法

ほとんどの場所に1を設定し、一部0を設定すると大半のパスでMEX値を2にできる。
あとは、0にする箇所を探していこう。
1である連結成分のサイズが増えると、その連結成分内のパスのMEX値が0になってよくない。
また、その境界値は最悪258である。

そこで、現在頂点を含む設定値1の頂点の連結成分のサイズを状態とし、木DPをしていこう。

int T,N;
vector<int> E[202020];
int C[2];
const int DI=600;

pair<vector<ll>,vector<ll>> dfs(int cur,int pre) {
	vector<ll> R[2];
	R[0].resize(1,1);
	R[1].resize(1,2);
	
	FORR(e,E[cur]) if(e!=pre) {
		auto P=dfs(e,cur);
		
		vector<ll> V[2],W[2];
		W[0]=P.first;
		W[1]=P.second;
		V[0].resize(min(DI,(int)R[0].size()+(int)W[0].size()),1LL<<60);
		V[1].resize(min(DI,(int)R[1].size()+(int)W[1].size()),1LL<<60);
		int i,j,l=V[0].size();
		FOR(i,2) {
			ll mi=*min_element(ALL(W[i^1]));
			FOR(j,R[i].size()) {
				chmin(V[i][j],mi+R[i][j]);
				for(int x=0;x<W[i].size()&&j+x+1<V[i].size();x++) chmin(V[i][j+x+1],W[i][x]+R[i][j]+(i+1)*(j+1)*(x+1));
			}
			
		}
		
		swap(V,R);
	}
	
	return {R[0],R[1]};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		
		ll sum=1LL*N*(N+1);
		auto p=dfs(0,0);
		ll mi=1LL<<60;
		FORR(a,p.first) mi=min(mi,a);
		FORR(a,p.second) mi=min(mi,a);
		cout<<sum-mi<<endl;
		
		
	}
}

まとめ

これ本番中に考察するの結構厳しいな。