ロボットの移動を \(K\) 回シミュレーションするのは、 \(K\) が非常に大きいので間に合いません。

各スイッチについて、ロボットが \(1\) 回通過するごとに L と R が切り替わります。

つまり、各頂点について最終的に何回ロボットが通過したかがわかれば、通過したロボットの数を足し合わせることで答えを求められます。

与えられるグラフは有向非巡回グラフなので、 \(1\) 体のロボットが複数回同じ頂点を通過することはありません。

そのため、トポロジカルソート順（今回は頂点の番号が小さい順）に求めることを考えます。

頂点 \(1\) を通過するロボットは \(K\) 体です。

頂点 \(i\) を通過するロボットの数 \(C_i\) が分かっているとき、 \(i \to L_i\) 、 \(i \to R_i\) に移動するロボットの数も計算できます。

頂点 \(i\) に到達したロボットたちは R \(\to\) L \(\to\) R \(\to\) L \(\to \cdots\) と順番に振り分けられるため、 \(i \to L_i\) に移動するロボットの数は \(\lfloor C_i / 2 \rfloor\) 、\(i \to R_i\) に移動するロボットの数は \(\lceil C_i / 2 \rceil\) とわかります。

これにより、頂点番号の小さい順に \(C_i\) を計算することができるので、 \(\sum_{i=1}^{N-1} C_i\) が答えになります。

計算量は全体で \(O(N)\) です。