report - 報告 (Report) Editorial by Nachia


各人からその報告先へ向いた有向辺を考えると、全体は functional graph です。ある閉路に含まれる人が受ける報告は閉路内ですべて共有されるので、 \(1\) 点にまとめます。すると、全体はいくつかの有向木になります。

仕事 \(i\) をする人が仕事 \(i\) の前に受ける報告の種類数は、頂点 \(i\) の部分木に含まれる、番号が \(i\) 未満の頂点の個数(と、もともと閉路だった部分で共有された分)です。有向木の頂点を dfs の行きがけ順に並べると、部分木はその列の区間で表されるので、問題全体は一点加算区間和クエリとなり(閉路を \(1\) 点にまとめたものも、うまく計算できています)、 binary indexed tree やセグメント木で処理できます。計算量は \(O(N \log N)\) です。

解答例

posted:
last update: