考察
各subtreeで必要なのは色ごとの出現回数と、その最大回数を持つ色数だけである。色番号がN以下なので hash map を使わず配列で頻度を持てる。
採用する候補: heavy child の集計を残し light child の Euler区間を追加し直す DSU on Tree を行い、cnt[color]、num[freq]、現在最大freqを配列で更新する。
各頂点が add される回数は root path 上の light edge 数+1で O(log N) に抑えられ、subtree query時にはちょうどそのsubtree全体の頻度表が残る。
棄却する候補: 各subtreeの色頻度 unordered_map を small-to-large merge する。
漸近的には可能でも N=2.5×10^6 では hash node の時間・空間定数が大きく、実用的な制限を超える。
最大subtree sizeの子をheavyにすると、light edgeを下るたびsubtree sizeが半分以下になり、一頂点の再追加回数が対数回になる。
色 x を追加すると num[cnt[x]]を減らし cnt[x]を増やして numを増やすだけで、mode回数 mx とその色数 num[mx]を即時取得できる。
最初のDFSでsubtree size、heavy child、Euler区間を求める。solve(v,keep) でlight childをkeep=false、heavyをtrueで処理し、light各Euler区間とvをaddする。答え(mx,num[mx])を保存し、keep=falseなら触れた範囲をresetする。
典型の発動条件
DSU on Tree
発動条件: 全subtreeの頻度統計を、色値域配列で軽量に求めたいとき。
heavy childのtableを再利用しlight subtreeだけ追加・削除する。
頻度の頻度配列
発動条件: 要素追加中にmode頻度とmode種類数を即時取得したいとき。
cnt[color]とnum[count]を同時更新する。
問題固有の要素
small-to-large の計算量だけでなく、巨大Nではcontainer一要素の実メモリを見て配列ベースの traversal reuseを選ぶ。
別の問題へ持ち帰る視点: mode queryは全色を走査せず、frequency histogramを持つと最大bucketだけで答えられる。
正当性
子の処理後に残すheavy部分木へ、他の子の全頂点と自分を足すと、集計対象はちょうど現在の部分木になる。頻度別個数の更新がこの集合の統計を保つため、最大頻度とその達成色数を正しく返す。keep=falseで集計を消せば兄弟の処理へ値を持ち越さない。
実装上の注意
- 再帰stackと巨大配列のmemoryを抑え、resetで全配列clearせず実際に追加したEuler範囲だけ戻す。num[0]の扱いをqueryに混ぜない。
復習の核
- light edge数が対数回となるsize半減証明と、solve(v,keep)終了時のtable内容を小木で追って確認する。
計算量と制約
時間
O(N log N)、sack法でlight側の再追加を半減回数へ課金。
空間
O(N)、Euler・色頻度・頻度別色数。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2.5 \times 10^6; 1 \leq p_i \lt i; 1 \leq c_i \leq N; 1 \leq \mathrm{seed} \lt 2^{31}; 2 \leq M \leq \min(N, 10^5); 1 \leq F \leq N; 1 \leq q_i \lt i; 1 \leq d_i \leq N; All input values are integers.
出典