Codeforces #562 Div1 D. Anagram Paths

問題設定がややこしい。
https://codeforces.com/contest/1168/problem/D

問題

根付き木を成すグラフが与えられる。なお、子頂点の数は２以下である。
各辺には1つの文字が設定される。ただし、任意の文字を取れる"?"が入ることもある。

以下のクエリに順次答えよ。

• クエリでは、1つの辺を選択しその文字を書き換える。その後、以下に答えよ。
  • 各Leafには、根からそこまでに至るパス上の文字を連結させた文字列が設定されているものとする。
  • 全Leafが互いにアナグラム、すなわち並べ替えたら同じ文字列となりうるか判定せよ。
  • もしなりうるなら、各文字の最大登場回数f(c)に対しsum(f(c)*ind(c))を求めよ。
  • (各cに対しf(c)を求める過程で、"?"には異なる数を加えてもよい。

解法

まず全Leafが同じ深さにあることをチェックしよう。

次に、深さがあまり深くない場合を考える。
各頂点において、そのSubTree以下に登場する確定済み文字の個数をカウントしよう。
もし根頂点において、そのような文字数が深さをこえてしまうなら達成不可である。
そうでない場合、余った分だけ"?"に任意の文字を入れる猶予があるということである。

ただ上記処理は、更新クエリがO(Depth)かかる。
そこで、分岐の内一連の辺を圧縮してしまおう。
そうすると各クエリで考慮すべき深さは高々O(√N)で収まる。

int N,Q;
int P[202020],TP[202020],TG[202020];
char C[202020];
vector<int> E[202020];
int D[202020],TD;
set<int> MD;
int id;
int L[202020],R[202020];
set<int> ng;
int add[202020][2][26];
int dp[202020][26];
int sum[202020];

int update(int x,int c,int dif) {
	int t=L[x];
	x=TP[x];
	
	if(L[E[x][0]]<=t && t<R[E[x][0]]) add[x][0][c]+=dif;
	else add[x][1][c]+=dif;
	
	while(1) {
		sum[x]-=dp[x][c];
		if(E[x].size()==1) {
			dp[x][c]=dp[TG[E[x][0]]][c]+add[x][0][c];
		}
		else {
			dp[x][c]=max(dp[TG[E[x][0]]][c]+add[x][0][c],dp[TG[E[x][1]]][c]+add[x][1][c]);
		}
		sum[x]+=dp[x][c];
		
		if(sum[x]>TD-D[x]) ng.insert(x);
		else ng.erase(x);
		
		if(x==0) break;
		x=TP[x];
	}
	
}

void dfs(int cur,int depth) {
	D[cur]=depth;
	L[cur]=id++;
	TG[cur]=cur;
	if(cur) {
		if(E[P[cur]].size()==1) TP[cur]=TP[P[cur]];
		else TP[cur]=P[cur];
	}
	
	if(E[cur].size()) {
		FORR(e,E[cur]) dfs(e,depth+1);
	}
	else {
		MD.insert(D[cur]);
	}
	R[cur]=id;
	
	
	if(E[cur].size()==1) TG[cur]=TG[E[cur][0]];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>P[i+1]>>C[i+1];
		P[i+1]--;
		E[P[i+1]].push_back(i+1);
	}
	
	dfs(0,0);
	if(MD.size()>1) {
		FOR(i,Q) cout<<"Fou"<<endl;
		return;
	}
	TD=*MD.begin();
	FOR(i,N) if(i && C[i]!='?') update(i,C[i]-'a',1);
	while(Q--) {
		cin>>x>>s;
		x--;
		if(C[x]!='?') update(x,C[x]-'a',-1);
		C[x]=s[0];
		if(C[x]!='?') update(x,C[x]-'a',1);
		
		if(ng.size()) {
			cout<<"Fou"<<endl;
			
		}
		else {
			int sum=TD;
			FOR(j,26) sum-=dp[0][j];
			ll ret=0;
			FOR(j,26) ret+=(sum+dp[0][j])*(j+1);
			cout<<"Shi "<<ret<<endl;
		}
	}
	
}

まとめ

言われてみるとシンプルな解法なんだよな。