No.363

木を HL 分解して, 分解したパスごとに $(A_{i}, A_{i+1}, A_{i+2})$ が門松列になっているかを調べておく. 調べた結果を論理積を取る Sparse Table に突っ込んでおくことでパス内の任意の区間が門松列列になっているかどうかを確認できるようにしておく.

あとは $u, v$ の LCA $s$ を求め, $s-u, s-v$ が門松列列になるかどうかを確認し, さらに $s, u, v$ の近傍で門松列になるかどうかを確認する.