Educational Codeforces Round 2 E. Lomsat gelral

「データ構造をマージする一般的なテク」の練習にいいと思ったので紹介しておく。

各頂点が色$c_v$で塗られている木が与えられる。頂点$v$の部分木の中で最も現れる頻度の高い色をdominating colourと呼ぶことにする。 dominating colourは一つとは限らない。それぞれの頂点の部分木に対しdominating colourの総和を求めよ。

各頂点に

の情報を持たせて、「データ構造をマージする一般的なテク」*1をすればいい。

マージテクやるだけ。最初、部分木に含まれる色を重複しないように総和とる問題だと思ってたけど全然違ってた。