Codeforces ECR #144 : E. Colored Subgraphs

あけましておめでとうございます。
https://codeforces.com/contest/1796/problem/E

問題

木を成すグラフが与えられる。
ここで任意の点を根とした根付き木を考えるとき、以下を求めよ。

• 各点を彩色する。その際、同じ色の点同士は辺で連結していなければならない。
• 根頂点からの最短距離が同じ2点は、同じ色であってはならない。

木のコストとは、使用した頂点のうち頻度の最小値とする。
コストの最大値を求めよ。

解法

根頂点が決まっている場合、以下で彩色を決められる。
今見ている点をどの色で塗るかは、子頂点の色のうち、その色で塗られた頂点数が最小の物で塗ることにする。

あとはこれを全方位木DPにしていけばよい。

int T;
int N;
vector<int> E[202020];
int ma;
int M[202020];
int C[202020];

void dfs(int cur,int pre) {
	E[cur].erase(remove(ALL(E[cur]), pre), E[cur].end());
	if(E[cur].empty()) {
		M[cur]=1<<20;
		C[cur]=1;
	}
	else {
		M[cur]=1<<20;
		vector<int> Cs;
		FORR(e,E[cur]) {
			dfs(e,cur);
			M[cur]=min(M[cur],M[e]);
			Cs.push_back(C[e]);
		}
		sort(ALL(Cs));
		int i;
		for(i=1;i<Cs.size();i++) M[cur]=min(M[cur],Cs[i]);
		C[cur]=Cs[0]+1;
	}
}

void dfs2(int cur,int pc,int pm) {
	if(E[cur].empty()) {
		ma=max(ma,min(pc+1,pm));
	}
	else {
		multiset<int> Cs,Ms;
		if(pc!=-1) Cs.insert(pc),Ms.insert(pm);
		FORR(e,E[cur]) {
			Cs.insert(C[e]);
			Ms.insert(M[e]);
		}
		ma=max(ma,min({*Ms.begin(),*Cs.begin()+1,*next(Cs.begin())}));
		
		FORR(e,E[cur]) {
			Cs.erase(Cs.find(C[e]));
			Ms.erase(Ms.find(M[e]));
			int nc=*Cs.begin()+1;
			int nm=min(*Ms.begin(),(Cs.size()>1?*next(Cs.begin()):1<<20));
			dfs2(e,nc,nm);
			
			Cs.insert(C[e]);
			Ms.insert(M[e]);
		}
		
	}
}

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);
		}
		FOR(i,N) if(E[i].size()>1) x=i;
		dfs(x,x);
		ma=min(M[x],C[x]);
		dfs2(x,-1,0);
		cout<<ma<<endl;
	}
}

まとめ

考察はできても細かいとこ詰めるの結構しんどいな。