解説PDF では省かれている内容を説明します．

小課題 \(3\)

\(N \leq 8\) より \(M \leq 7\) なので，\(2^M\) 通りの向き付けを全て試せばいいです．

小課題 \(4\)

ある頂点 \(v\) を \(1\) つ決めたときに，それが \(A\) であるかは以下のように判定できます．

• \(v\) から DFS をして \(v\) と各頂点の距離を求める．
• \(v\) から離れるような向き付けを試す．これで Yes となる必要がある．
• \(v\) に隣接する辺のみについて \(v\) に向かうような向き付けを試す．これで No となる必要がある．

\(A\) から \(B\) のパスは \(v\) に隣接する辺を \(v\) から離れる向きで使うことを考えると，この方法が正当であることが確認できます．

よって，$v$ が $A$ かを $2$ 回のクエリで判定できます．これより高々 $2N$ 回で $A$ を特定できます．同様に，$B$ についても高々 $2N$ 回で特定できます．
全体で高々 $4N$ 回のクエリで解けます．頂点の index をシャッフルすることで期待値 $2N$ 回となりますが，運が良くないと小課題 $5$ は通らないと思います．

小課題 \(5\)

全頂点について，その頂点から離れる向き付けと，その頂点に向かう向き付けを試します．

これで一意に定まります．実際に各パスについて結果が一致するか確認すればいいです．全体で $2N$ 回のクエリとなります．

小課題 \(6\)

\(v\) から離れるような向き付けが Yes となるような \(v\) を \(1\) つ取ります．これは全て試すことで高々 \(N\) 回で見つけられます．

各頂点について $v$ からの距離で順位をつけます．(タイブレークは適当で構いません．)
$v$ から $i$ 番目までに近い頂点のみについては到達できるような向き付けが可能です．$v$ から離れるような向き付けについて，遠い方の辺から $v$ に向かうように反転させるイメージです．
これを用いることで，Yes と No の境目を二分探索できます．

これにより $\log N$ 回で $B$ を特定できます．
$A$ についても $v = B$ として考えれば同様に $\log N$ 回で特定できることが分かります．

全体で $N + 2 \log N$ 回のクエリとなります．なお，小課題 $4$ で頂点の index をシャッフルすれば期待値 $N$ 回で $A$ を特定できるため，期待値 $N + 2 \log N$ 回となりますが，これも運が良くないと小課題 $6$ は通らないと思います．

小課題 \(7\)

Yes となる向きづけを得るという方針は変わりません．
根を \(r\) とし，部分木についてラベル \(X, Y\) のいずれかを割り振ります．

$X \rightarrow r \rightarrow Y$ の向き付けをします．これが Yes ならば目標は達成されます．No ならば $X \leftarrow r \leftarrow Y$ の方向の向き付けをします．これが Yes ならばやはり目標は達成されます．
共に No だったとします．このとき，$A$ と $B$ について，それぞれが属する部分木のラベルが同じであることが言えます．異なる部分木に属している可能性があることに注意してください．

よって，$r$ とラベル $X$ の部分木を集めて得られる部分木 $T_X$ と $r$ とラベル $Y$ の部分木を集めて得られる部分木 $T_Y$ と定めて，$T_X, T_Y$ について再帰的に解くことができます．
$\frac{1}{3}$ 重心分解を考えると，$r$ や各部分木のラベルを適切に定めると $|T_X|, |T_Y| \leq \frac{2}{3}N$ とできます．

この方針により $2$ 回のクエリでサイズを高々 $\frac{2}{3}$ とできるため，全体では $4 \log N$ 回程度のクエリとなります．

小課題 \(8\)

小課題 \(7\) の方針で考えます．適当に全域木を取ります．全域木に含まれない辺についても適切に向き付けすることで木と同じ場合で考えられます．
よって，これも \(4 \log N\) 回程度のクエリで可能です．

なお，解説 PDF では $3$ 回のクエリでサイズを高々 $\frac{1}{2}$ とする方針になっています．再帰する過程において，部分木のサイズに着目することで再帰後のサイズが具体的に最大でいくらになるかが求まります．
これにより $1$ 回のクエリあたりでサイズがどれだけになるかというのが両方針について評価できるため，どちらを採用するのが最適かが分かります．

これにより $3.465 \log N$ 回程度のクエリとなる解法が得られます．

余談

このように解法について，高々この回数のクエリで解けるという上界の評価は得られます．しかし，実際に上界，もしくはそれに近い回数となる木や一般グラフ (ラフに言うならば強いテストケース) が存在するかというのはまた別の問題かのように思えます．
提案する際にこれらの問題についても考えましたが，良い結論は得られませんでした．