与えられた \(N\) 頂点の木を、頂点 \(S\) を根とした根付き木ととらえて考えます。

結論から言うと、木のそれぞれの頂点 \(j\) についての質問の答えは、 \(\left( \mathrm{LCA}(j, T) \text{ と } j \text{ との距離} \right) +1\) となります。ここで、 \(\mathrm{LCA}(u, v)\) は頂点 \(u\) と \(v\) の最小共通祖先を指し、\(x\) と \(y\) との「距離」とは、頂点 \(x\) から \(y\) まで最短経路で移動したときに通る辺の数を指します。

上記の証明をします。 \(u\) から \(v\) へのパスを \(P(u, v)\) と書くことにし、また \(a = \mathrm{LCA}(j, T)\) とします。

木の性質より、\(P(j, T)\) は \(P(j, a)\) と \(P(a, T)\) に分解できます。これらのパスについて以下が成り立ちます。

• \(P(j, a)\) に含まれる辺は、すべて \(P(S, j)\) に含まれる
  • \(S\) が根であることと、\(a\) が \(j\) の祖先であることから従います
• \(P(a, T)\) に含まれる辺は、すべて \(P(S, j)\) に含まれない
  • \(T\) から根に向けて順に頂点をたどったときに、初めて \(P(S, j)\) 上に乗ったときの頂点が \(a\) であることから従います

よって \(P(j, a)\) に含まれる頂点の数が求められればよく、これは \(j\) と \(a\) との距離から求められます。

全体の計算量は \(O(N \log N)\) です。

実装例 (C++): https://atcoder.jp/contests/codequeen2023-final-open/submissions/44185946