\(S\) を始点とするBFS、 \(T\) を始点とするBFSだけで解くことができます。

前者(\(S\) を根とする木)における頂点 \(v\) の親を \(P_S (v)\)、後者を \(P_T(v)\) とします。親が存在しないとき \(-1\) とでもしておきます。

問題文での \(j\) において、求めたいものを \(ans(j)\) とすると、以下がなりたちます。

\[ ans(j) = \left\{ \begin{array}{l} \displaystyle 1 \;\;\; &(P_S(j) \neq P_T(j) または P_S(j) = -1 または P_T(j)=-1) \\ ans(P_S(j)) + 1 &( P_S(j) = P_T(j) かつ P_S(j) \neq -1 ) \end{array} \right. \]

これはメモ化再帰を使うことで、それぞれの \(j\) について全体で \(O(N)\) で求めることができます。

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