3 - スパイ (Spy) 解説 by hirayuu_At

別解

IOI社のリーダーが同じものを同時に処理することを考えます。

このとき、「JOI社の人はそれぞれいくつのプロジェクトに所属しているか?」を高速に求める必要があります。

これはABC138 - Dと全く同じ問題であり、木上で累積和をとることで求められます。

IOI社の人間への寄与は、リーダーを起点に愚直にDFSをしても全く問題ありません。

計算量は \(O(M+N^2)\) であり、本問題の制約下でこれは十分高速です。