3 - スパイ (Spy) Editorial
by
hirayuu_At
Editorial for printing
別解
IOI社のリーダーが同じものを同時に処理することを考えます。
このとき、「JOI社の人はそれぞれいくつのプロジェクトに所属しているか?」を高速に求める必要があります。
これはABC138 - Dと全く同じ問題であり、木上で累積和をとることで求められます。
IOI社の人間への寄与は、リーダーを起点に愚直にDFSをしても全く問題ありません。
計算量は \(O(M+N^2)\) であり、本問題の制約下でこれは十分高速です。
posted:
last update: