Codeforces #763 : Div2 E. Middle Duplication

ようやく2021年度の終わりが見えてきた…。
https://codeforces.com/contest/1623/problem/E

問題

1番の頂点を根とする根付き木が与えられる。
各点には、左右高々2つまでしか子頂点が付かない。

各点vには1文字のラベルC(v)が設定されている。
この時、頂点vのSubTreeに対応する文字列F(v)は以下のように定義される。
L(v)、R(v)を左右の子頂点として、
F(v) := F(L(v)) + C(v) + F(R(v))

ここで、一部選択した点vに対し、C(v)をC(v)+C(v)の2文字にすることができる。
ただし、その場合親頂点も2文字にしなければならない。
また、2文字にできる頂点数は最大K個である。
この時、F(1)を辞書順最小化せよ。

解法

まずはじめてDFS順でF(v)がどうなるかを考える。
各頂点のラベルについて、次に現れる異なるラベルが、今より辞書順で後ろであれば、ラベルを2文字化する意味がある。

ある点を2文字化する場合、左側の子でたどってきた場合の各親も合わせて2文字化しなければいけないことを踏まえながらDFSしよう。

int N,K;
string S;
int L[202020];
int R[202020];
int should[202020];
vector<pair<char,int>> T;
int dup[202020];

void dfs(int cur) {
	if(L[cur]) dfs(L[cur]);
	T.push_back({S[cur-1],cur});
	if(R[cur]) dfs(R[cur]);
}

int dfs2(int cur,int cost) {
	if(cost>K) return 0;
	if(L[cur]) {
		dup[cur]=dfs2(L[cur],cost+1);
	}
	if(dup[cur]==0&&should[cur]) {
		K-=cost;
		dup[cur]=1;
	}
	if(dup[cur]&&R[cur]) dfs2(R[cur],1);
	
	
	return dup[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) {
		cin>>L[i+1]>>R[i+1];
	}
	dfs(1);
	for(i=N-2;i>=0;i--) {
		if(T[i].first<T[i+1].first) {
			should[T[i].second]=1;
		}
		if(T[i].first==T[i+1].first) {
			should[T[i].second]=should[T[i+1].second];
		}
	}
	dfs2(1,1);
	FOR(i,N) {
		cout<<T[i].first;
		if(dup[T[i].second]) {
			cout<<T[i].first;
		}
	}
	cout<<endl;
	
}

まとめ

Div2とはいえボス問の割に正答者多いな。