Codeforces Round #458 (Div. 1 + Div. 2, combined) E. Palindromes in a Tree

お題箱より。

問題概要

$n$ 頂点の木が与えられ、各頂点には a から t までのうち1文字のアルファベットが書かれている。

この木の2点間を結ぶパスであって、「通過する頂点のアルファベットを並び替えることで回文にすることができる」ようなものをpalindromicなパスと呼ぶ。

各頂点 $i$ について、頂点 $i$ を通るpalindromicなパスの数を求めよ。ここで始点と終点が同一であるパス $(a, a)$ はカウントし、始点と終点を入れ替えたパス $(a, b), (b, a)$ は1つのみカウントするものとする。

制約

$1 \le n \le 2\times 10^{5}$
各頂点に書かれたアルファベットは a 以上 t 以下
グラフは木である

解説の前に

この問題は重心分解そのものを学ぶ問題としてはあまり適さないと思います。重心分解の実装や使い方については、まず

ツリーの重心分解 (木の重心分解) の図解 - Qiita

こちらの記事で実装について理解し、

競技プログラミングにおける重心分解問題まとめ - はまやんはまやんはまやん

こちらの記事の（入門）と書かれている問題などで使い方を習得することをおすすめします。

解法

パスの数え上げ→重心分解を考えてみる

「木について、ある条件を満たすパスの個数を求めよ」というタイプの問題でよく使うのが重心分解です。重心分解でパスの本数を数える問題は、

まず木の重心を求め、その重心を通るようなパスだけについて条件を満たすものを数えた後、その重心を取り除くことでできる部分木に対して同じ処理を再帰的に行う

という構造になっています。

重心分解でパスの数え上げが上手くいくのは、数えたいパスが以下のような性質を持っている場合です。

各頂点 $v$ と重心を結ぶパスについて何らかの特徴量 $B_{v}$ が計算できて、重心を挟む2頂点間のパス $(v, u)$ がカウント対象となる条件が $B_{v}, B_{u}$ で表現できる。特に、一方の端点の特徴量 $B_{v}$ を固定した時にもう一方の端点の特徴量 $B_{u}$ が満たすべき条件が容易に定まる。

どういうことなのか、今回の問題で具体的に説明していきましょう。

並び替えて回文にできるかどうか判定するので、パスの特徴として必要なのは各アルファベットの登場回数の偶奇だけです。アルファベットの種類は20個なので、これは長さ20のビット列として表現できます。パスがpalindromicである条件は、このビット列において立っているビットが0個または1個であることです。

重心を決め、重心のアルファベットに対応するビットだけを立てたビット列を $C$ とします。そして重心以外の頂点 $v$ について「（重心を除いて）重心からその頂点までのパスに対応するビット列」 $B_{v}$ が求められたとします。