読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 2 E. Lomsat gelral

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

問題文

codeforces.com

Editorial: http://codeforces.com/blog/entry/21827

問題概要

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

解法

各頂点に

  • 色$c$をキーとした多重集合
  • dominating colour の総和
  • dominating colour の頻度

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

Educational Codeforces Round 2 E. Lomsat gelral

感想

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