社員同士の上司-部下の関係をグラフに表してみましょう。
すると、それはwarabi君を根とした木(頂点の番号に社員の番号が対応)であることがわかります。
その時、「全員に指示が出せる社員」という条件は「どの頂点からも、親方向にたどっていってたどり着ける頂点」
と言い換えられます。
この「親をたどってたどり着ける頂点」のことを共通祖先と呼びます。
共通祖先を求めるのには、LCAというアルゴリズムが有効で、で求めることができます。
しかし、これは任意の二頂点に限ったことなので、結局クエリの区間分の計算量がかかってしまい、全体の計算量はになってしまいます。
これを高速化するのに、segment-treeを使い、二つのノードの親をその共通祖先...と
することで、前処理に、区間クエリにで答えることができます。これは十分に高速です。