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

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

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

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

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

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

計算量は です。