ある頂点を根とする根付きとして見て、オイラーツアーしておきます。
を固定して考えます。 と の位置関係は、 の部分木に が存在する または の部分木に が存在しない の 2 通りです。
頂点番号が大きい方から見ます。
前者の場合は、 が出現したときに、部分木のうち出現済みの頂点数が分かればよくて、オイラーツアー+Segtreeでできます。 の子のうち部分木に が含まれる木以外の任意の未出現の頂点が の候補です。 ある部分木以外に加算できればよくて、同様にSegtreeでできます。
後者の場合も同様です。 が出現したときに、部分木以外の出現済み頂点が分かれば良いです。 の部分木の任意の未出現の頂点が の候補です。 ある部分木に加算できればよいです。
はその時点で加算された値を取ればよいです。
計算量は です。