木のタプル2

ある頂点を根とする根付きとして見て、オイラーツアーしておきます。

$b$ を固定して考えます。 $b$ と $c$ の位置関係は、$b$ の部分木に $c$ が存在する または $b$ の部分木に $c$ が存在しない の 2 通りです。

頂点番号が大きい方から見ます。

前者の場合は、$b$ が出現したときに、部分木のうち出現済みの頂点数が分かればよくて、オイラーツアー+Segtreeでできます。$b$ の子のうち部分木に $c$ が含まれる木以外の任意の未出現の頂点が $a$ の候補です。 ある部分木以外に加算できればよくて、同様にSegtreeでできます。

後者の場合も同様です。 $b$ が出現したときに、部分木以外の出現済み頂点が分かれば良いです。$b$ の部分木の任意の未出現の頂点が $a$ の候補です。 ある部分木に加算できればよいです。

$a$ はその時点で加算された値を取ればよいです。

計算量は $O(N \log N)$ です。