首先可以注意到题面中的这个条件：
对于三座城市 \(x\)，\(y\)，\(z\)，若 \(x\Rightarrow z\) 且 \(y\Rightarrow z\)，那么有 \(x\Rightarrow y\) 或 \(y\Rightarrow x\)。
这就代表着如果存在边 \(x\rightarrow z\) 和 \(y\rightarrow z\)，假设存在 \(x\Rightarrow y\) 那么删去边 \(x\rightarrow z\) 也不影响图的任意两点的连通性。
所以考虑缩点跑拓扑排序，对于一个入度大于 \(1\) 的点，只保留拓扑排序是最后碰到的那条入边。因为题目条件保证，所以这样操作之后原图就变成了一颗外向树。
令集合 \(S\) 表示 \(s\) 能到达的点的点集，集合 \(T\) 表示 \(t\) 能到达的点的点集。
可以注意到，一个点 \(u\) 可以在游行时经过的充要条件是 \(u\in S\cap T\)。证明显然。
如果 \(k=0\)，那么 \(S\) 就是 \(s\) 及其子树组成的集合，\(T\) 就是 \(t\) 到根的链的点集。用树剖+线段树的方式在 \(t\) 到根的链上标记然后统计 \(s\) 的子树内有多少个被标记的点即可。
如果 \(k\neq0\)，考虑加入一条边 \(a\rightarrow b\) 对集合 \(S\)，\(T\) 的影响。
- \(a\in S\Rightarrow b\in S\)
- \(b\in T\Rightarrow a\in T\)
枚举每一个 \(a_i\)，\(b_i\) 处理即可。但是可能会出现加边顺序问题，所以需要 \(O(k^2)\) 解决。