Codeforces #949 : Div2 F. Turtle and Paths on a Tree

これはなかなか厳しい。
https://codeforces.com/contest/1981/problem/F

問題

二分木を成す無向グラフが与えられる。
また、各点には整数値が設定されている。
このグラフを、複数のパスでカバーするようにしたい。
その時、各パス上の頂点の設定値のmex値の総和を考える。
この値の最小値を求めよ。

解法

f(v,i) := vのsubtreeにおいて、vの上向きに進めるパス上に、整数iを設定された頂点がない場合、mex値の総和
として、この値を葉から順に更新していく。
この時、iはO(N)通り考える必要はなく、O(N/logN)程度まで考えればよい。

int T,N,M,A[202020];
vector<int> E[202020];
int dp[25252][4000];

void dfs(int cur) {
	int i;
	if(E[cur].empty()) {
		for(i=1;i<=M;i++) dp[cur][i]=(i==A[cur])?(1<<28):0;
	}
	else if(E[cur].size()==1) {
		int x=E[cur][0];
		dfs(x);
		int mi=1<<28;
		for(i=1;i<=M;i++) if(i!=A[cur]) mi=min(mi,dp[x][i]+i);
		if(cur==0) {
			cout<<mi<<endl;
		}
		else {
			for(i=1;i<=M;i++) dp[cur][i]=(i==A[cur])?(1<<28):min(dp[x][i],mi);
		}
	}
	else {
		int x=E[cur][0];
		int y=E[cur][1];
		dfs(x);
		dfs(y);
		int mix=1<<28,miy=1<<28,k=1<<28;
		for(i=1;i<=M;i++) if(i!=A[cur]) {
			mix=min(mix,dp[x][i]+i);
			miy=min(miy,dp[y][i]+i);
			k=min(k,dp[x][i]+dp[y][i]+i);
		}
		k=min(k,mix+miy);
		if(cur==0) {
			cout<<k<<endl;
		}
		else {
			for(i=1;i<=M;i++) dp[cur][i]=(i==A[cur])?(1<<28):min({dp[x][i]+miy,dp[y][i]+mix,k});
		}
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		M=min(N+2,3900);
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x;
			E[x-1].push_back(i+1);
		}
		dfs(0);
	}
}

まとめ

考えるmex値が意外に小さく済むっての、見積もりが難しいな…。