木の直径など、遠い頂点対から貪欲にマッチングさせていけば何となくよさそう?
その場合、最終的に木の真ん中らへんの頂点が残る。
言い換えると、各ペアを結んだパスは、必ず木の真ん中らへんを通るものとなる。
木の真ん中というと、木の重心が連想される。
重心は、その頂点を根とすると全ての部分木のサイズが $N/2$ 以下になる頂点のことなので、
重心を必ず通るような頂点対をマッチングさせていけば、必ず $N/2$ ペアまで構築できる。
($N$ が偶数で重心が1点の時は、残った1頂点と重心をペアとする)
この発想が正しいか確認する。
木の重心を通らないペア $P$ が答えの1つにあるとする。
この時必ず、木の重心で分解したときに、両頂点とも $P$ と異なる部分木に含まれるようなペアが存在する。
(存在しないと数が合わなくなるので)
◎--o, ,-o ○: 木の重心 o-o-○-o-●-o ◎: 木の重心を通らないペア ◎--o' `-● `-o ●: ◎と異なる部分木にある他のペア
なら、◎-● を結ぶ2組のペアにつなぎ替えて損しない。
よって、最適解の1つには、全てのペアが重心を経由しているものが存在する。
木の重心を求めるのは既によく知られた方法があり、適当な頂点から部分木のサイズを求める木DPをおこなえば分かる。 (上述のけんちょん氏の記事など参照)
重心からの各部分木に含まれる頂点が分かっているとき、これらをどうやってペアにするのがよいか?
適当にやると、頂点数が多い部分木が1つだけ残ってしまい、失敗しかねない。
全て $N/2$ 以下であることが分かっているので、 部分木の頂点リストをflattenし、$i$ と $i+N/2$ 番目をそれぞれペアにしていけば、楽に実装できる。
部分木1に含まれる頂点番号 [ 3, 7, 5, 8, ... ] 部分木2に含まれる頂点番号 [ 9, 3, 6, ... ] 部分木3に含まれる頂点番号 [ 2, 0, 1, ... ] ↓flatten [ 3, 7, 5, 8, ..., 9, 3, 6, ..., 2, 0, 1, ..., 重心 ] ^ ^ ^ ^ N/2 ずつ離れた頂点をペアにしていく ^ ^
この発想が出ず、少し手間のかかる実装をしてしまった。
まぁ、基本方針が合ってたのでよし。
検索文字列 $T$ が複数あるということで、Aho-Corasickが連想されるが、下手に実装するとTLEする。
■TLE解法 各 Ti の終端ノードに「自身は Ti の終端ノードである」という情報を持たせ、 S のTrie上での遷移の過程でそのノードに訪れたとき、クエリ i の答えに1加算するような実装だと、 S: aaaaaaaaaaaa... (500000の長さ) T: a, aa, aaa, ... (約1000個のクエリ) のような時、以下のようなTrie木が構築される。 (root)--(a)--(aa)--...--(a x 999)--(a x 1000), ↑______________/ failure 末端の(a x 1000)は全てのTiの終端であるため、 訪れたとき、1000個のクエリの答えに加算処理が走ってしまう。 末端に到達したらループするため S の1文字毎に1000個の処理が走り、 全体で O(|S| √Σ|T_i|)、5x10^8 くらいかかってしまう。
ここでは逆に、「$S$ からの遷移の過程で、このノードは何回訪れられた」という情報 visited_count を記録する。
(下記の補正を行った上で)各 $T_i$ の終端ノードの visited_count が、そのままクエリ $i$ の答えとなる。
Aho-Corasick法では、$T_i$ の終端ノードが、他の $T_j$ 次第で $S$ に含まれているのに訪れられないことがある。
(root)----(a)----(ab)----(abc) S = babc, T = [abc, bc, c] の場合、Sの遷移は | ↙~~~' ↙~~~' (root)→(b)→(root)→(a)→(ab)→(abc) |------(b)----(bc) の順に訪れられる | ↙~~~' `------(c) "abc" の方が長くマッチングしているので優先され、 "bc" "c" は含まれているが訪れられない。
これをfailure-linkを使って補正する。
$S$ からの遷移終了後、葉から「自身の failure-link 先の visited_count」に「自身の visited_count」を加算していけばよい。
上記の例の場合は、(abc) から (bc) に visited_count が加算され、
またその後 (bc) から (c) にも加算され、(bc),(c) の visited_count がちゃんと $1$ となる。
failure-linkを辿ると必ず深さが浅いノードに遷移するので、rootからの深さが深い順に行うと正しく補正できる。
計算量は $O(|S| + \sum{|T_i|})$ となる。
$S$ のSuffix-Arrayを構築しておけば、ある文字列 $T$ の出現回数は、二分探索で求められる。
文字列の二分探索なので、1回毎に最大 $|T_i|$ の計算がかかり、 クエリ部分の計算量は全体で $O(\sum{|T_i|}\log{|S|})$ となるが、間に合う。
$S$ のSuffix-Array内における、$T_i$ の“bisect_left 的な位置”と、“bisect_right 的な位置”の差が答えとなる。
また、二分探索が不要な実装として、$S$ と $T$ を全て結合したSuffix-Arrayを構築する方法もある。
各文字を $1~26$ に変換して整数リストにした上で、区切り文字として $0,27,28$ を使って、
のように結合した文字列 $U$ に対して Suffix-Arrayを構築する。
こうすると、必ずSuffix-Arrayの中では
の順に並ぶ。①,③の $U$ 上の開始位置を求めておけばSuffix-Array上の位置がわかるため、挟まれた②の個数が答えとなる。
ただし、①と③の間には他のクエリのSuffixも含まれうるので、それは数えてはいけない。
Suffix-Array構築後、$S$ から始まるものだけを抽出して累積和などで整理しておけばよい。
計算量は $O(|S|+\sum{|T_i|}+\sigma)$(※$\sigma$: 文字の種類数=29)。
なお、ac-library for python の suffix_array() には引数に文字種数 $\sigma$ に相当する“upper”を与えられるが、これを省略すると3秒以上かかりTLEした。
ちゃんと $28$ を設定すると半分以下の1300msで通ったので、高速化のためには重要なパラメータである。