Codeforces #1048 : Div1. C2. Maple and Tree Beauty (Hard Version)

これはまぁすんなり解けたかな。
https://codeforces.com/contest/2138/problem/C2

問題

N頂点の根付き木が与えられる。
また、整数Kが与えられる。
N点中K点にラベル0、残り(N-K)点にラベル1を振る。

各葉頂点に対応する文字列を、根頂点から葉までのパス上のラベルを連結したものとする。
こうしてできた文字列のうち、最大の共通部分列の長さを求めよ。

解法

木の深さが深いほど、同じ共通部分列を作るために必要な0/1の数が増える。
よって、浅いところから0/1を敷き詰めて行き共通部分列を作ることを考える。

あとは深さごとの頂点数を求め、それぞれに0/1を敷き詰めて行ったときに、0をK個以下、1を(N-K)個以下にできるかDPで判定していけばよい。

int T,N,K;
int P[202020];
vector<int> E[202020];
int D[202020];
int ND[202020];
int A[402020];
int S[402020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		K=min(K,N-K);
		FOR(i,N) {
			E[i].clear();
			ND[i]=0;
		}
		ND[0]=1;
		int ma=1<<20;
		FOR(i,N-1) {
			cin>>P[i+1];
			P[i+1]--;
			E[P[i+1]].push_back(i+1);
			D[i+1]=1+D[P[i+1]];
			ND[D[i+1]]++;
		}
		
		FOR(i,N) if(E[i].empty()) ma=min(ma,D[i]);
		map<int,int> M;
		FOR(i,ma+1) M[ND[i]]++;
		
		FOR(i,K+1) A[i]=0;
		A[0]=1;
		int ret=0;
		int ns=0;
		int step=0;
		FORR2(a,b,M) {
			FOR(i,K+1) S[i]=0;
			FOR(i,K+1) if(A[i]) {
				S[i]++;
				if(i+a*(b+1)<=K) S[i+a*(b+1)]--;
				int la=K-i;
				int lb=N-K-(ns-i);
				int add=min(b,la/a+lb/a);
				ret=max(ret,step+add);
			}
			
			FOR(i,K+1) {
				A[i]=S[i]>0;
				if(i+a<=K) S[i+a]+=S[i];
			}
			ns+=a*b;
			step+=b;
			
		}
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

これEasy/Hardで問題分ける意義がよくわからなかった。