AtCoder ABC #293 : Ex - Optimal Path Decomposition

本番最初問題読み間違えてしまった。
https://atcoder.jp/contests/abc293/tasks/abc293_h

問題

木を成すグラフが与えられる。
各頂点に任意の色を塗るとき、以下を満たす最小のKを求めよ。

• 同じ色の頂点群は、単一のパスを成す。
• 任意のパス上に現れる色の種類はK以下である。

解法

Kを二分探索しよう。
あとは木DPで解く。

• 現頂点が(同じ色の頂点群のパスの)端点であるとき、現頂点から葉までのパスの色の種類数の最大値の最小値
• 現頂点が(同じ色の頂点群のパスの)端点でないとき、現頂点から葉までのパスの色の種類数の最大値の最小値

を考えて葉側から埋めて行こう。
出来れば、上記現頂点がパスの端点であるときの方がうれしい。というのも親側と同じ色にできる可能性があるからである。
そのため、端点でないときの方が、上記最大値の最小値が小さくならない限りでは、端点であるようにしていこう。
その際、現頂点は、子頂点のうち上記DP値が大きい頂点でかつ端点である点のうち0～2個と同じ色になるようにしていく。

int N;
vector<int> E[202020];
int K;
int ok;

int dp[202020];
int t[202020];

void dfs(int cur,int pre) {
	if(E[cur].size()==1&&E[cur][0]==pre) {
		dp[cur]=1;
		t[cur]=1;
		return;
	}
	int ma=0;
	vector<int> X[2];
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		X[t[e]].push_back(dp[e]);
	}
	sort(ALL(X[0]));
	sort(ALL(X[1]));
	reverse(ALL(X[0]));
	reverse(ALL(X[1]));
	
	if(X[1].size()<=1) {
		vector<int> Y;
		FORR(a,X[0]) Y.push_back(a);
		FORR(a,X[1]) Y.push_back(a-1);
		sort(ALL(Y));
		reverse(ALL(Y));
		if(Y[0]+1>K) ok=0;
		if(Y.size()>=2&&Y[0]+Y[1]+1>K) ok=0;
		t[cur]=1;
		dp[cur]=Y[0]+1;
	}
	else {
		X[1][0]--;
		vector<int> Y;
		FORR(a,X[0]) Y.push_back(a);
		FORR(a,X[1]) Y.push_back(a);
		sort(ALL(Y));
		reverse(ALL(Y));
		int cand=Y[0]+1;
		if(Y[0]+1>K) cand=1<<20;
		if(Y.size()>=2&&Y[0]+Y[1]+1>K) cand=1<<20;
		
		X[1][1]--;
		Y.clear();
		FORR(a,X[0]) Y.push_back(a);
		FORR(a,X[1]) Y.push_back(a);
		sort(ALL(Y));
		reverse(ALL(Y));
		if(Y[0]+1>K) ok=0;
		if(Y.size()>=2&&Y[0]+Y[1]+1>K) ok=0;
		if(Y[0]+1<cand) {
			t[cur]=0;
			dp[cur]=Y[0]+1;
		}
		else {
			t[cur]=1;
			dp[cur]=cand;
		}
		
		
	}
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	int ret=N;
	for(i=20;i>=0;i--) {
		K=ret-(1<<i);
		if(K>=1) {
			ok=1;
			dfs(0,0);
			if(ok) ret=K;
		}
	}
	cout<<ret<<endl;
}

まとめ

丁寧にやれば解けてたな…しっかりやればよかった。