Codeforces #383 Div1 D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

このマージテクはしらんわ…。
http://codeforces.com/contest/741/problem/D

問題

N個の根付き木を成すグラフがある。
各辺には１文字のアルファベットが設定されている。
各頂点に対し、そのサブツリー上のパスで、経路上のアルファベット群を並べ替えると回文にできるようなものの最長の長さを求めよ。

解法

各頂点xに対し、xをLCAとするようなパスの両端u-vのうち最長のものを求めることを考える。
根から頂点yまでに登場するアルファベットの登場回数の偶奇をbitmaskとして考える。
B[x]をそのbitmask、D[x]をxの根からの深さとする。
xの異なる子のsubtreeにある2頂点uとvのbitmaskのハミング距離が1以下の場合、D[u]+D[v]-2*D[x]の最大値が最長のパスを構成する両端u-vとなる。

あとはマージテクの要領で、subtree中に登場する頂点のbitmaskと対応する深さの最大値を葉から順に処理していけばよい。
…ただしこの問題はかなり入力が大きく、この最大値の管理はmapでもunordered_mapでもTLEする。

そこはEditorialにある通り、各頂点の集合を管理する下記のテクを使おう。
一応これも大きなSubtreeのデータに、小さなSubtreeのデータを合わせていくマージテクの亜種といえる。
[Tutorial] Sack (dsu on tree) - Codeforces

以下のコードではオイラーツアーでSubtree内の頂点群を容易にiterate可能にし、小さいsubtreeから先に処理を行っている。
今回の問題ではmapやunordered_mapの代わりに配列で済むようになるのでTLに間に合う。

int N;
int P[505050];
int mask[505050];
char C[505050];
int D[505050];
vector<pair<int,char>> E[505050];
int ret[505050];

int id;
int L[505050],R[505050],ID[505050];


int ma[1<<22];

void dfs(int cur,int pre) {
	L[cur]=id++;
	ID[L[cur]]=cur;
	FORR(r,E[cur]) if(r.first!=pre) {
		mask[r.first] = mask[cur] ^ (1<<r.second);
		D[r.first] = D[cur] + 1;
		dfs(r.first,cur);
	}
	R[cur]=id;
}

void dfs2(int cur,int pre,int keep) {
	int big=-1,i;
	FORR(r,E[cur]) if(r.first!=pre) {
		if(big==-1 || R[r.first]-L[r.first]>R[big]-L[big]) big = r.first;
	}
	FORR(r,E[cur]) if(r.first!=pre && r.first!=big) dfs2(r.first,cur,0);
	if(big>=0) dfs2(big,cur,1);
	FORR(r,E[cur]) if(r.first!=pre && r.first!=big) {
		for(int x=L[r.first];x<R[r.first];x++) {
			ret[cur] = max(ret[cur], ma[mask[ID[x]]]+D[ID[x]]-2*D[cur]);
			FOR(i,22) ret[cur] = max(ret[cur], ma[(1<<i)^mask[ID[x]]]+D[ID[x]]-2*D[cur]);
		}
		for(int x=L[r.first];x<R[r.first];x++) {
			ma[mask[ID[x]]] = max(ma[mask[ID[x]]],D[ID[x]]);
		}
	}
	ma[mask[cur]] = max(ma[mask[cur]], D[cur]);
	ret[cur] = max(ret[cur], ma[mask[cur]]-D[cur]);
	FOR(i,22) ret[cur] = max(ret[cur], ma[(1<<i)^mask[cur]]-D[cur]);
	FORR(r,E[cur]) if(r.first!=pre) ret[cur] = max(ret[cur], ret[r.first]);
	
	if(keep==0) {
		for(int x=L[cur];x<R[cur];x++) ma[mask[ID[x]]] = -1<<30;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>P[i+1]>>C[i+1];
		C[i+1]-='a';
		P[i+1]--;
		E[P[i+1]].push_back({i+1,C[i+1]});
	}
	
	dfs(0,-1);
	FOR(i,1<<22) ma[i]=-1<<30;
	dfs2(0,-1,1);
	
	FOR(i,N) _P("%d%c",ret[i],(i==N-1)?'\n':' ');
	
}

まとめ

勉強になりました。
でもmapやunordered_mapで通る制限でCで出してもいい気がしたな…。