初期状態から「よい操作」を1回行った後、各コマをさっきと逆方向に動かせば、それも「よい操作」で、初期状態に必ず戻る。
これが一意に決まるのだから、操作は、初期状態と（一意に決まる）1回操作後の状態を交互に繰り返すしかないことがわかる。
木DPで解けそうな見た目をしているので、その方向で考える。
頂点1を根とした根付き木として、各頂点に対して、
奇数回・偶数回目の操作後にコマはある/ない
ある場合、それは次に子に動く/親に動く
ない場合、次に子からコマが来る/親からコマが来る
などで場合分けして、その時々の、部分木内のコマの置き方のパターン数をDPすればよさそうだが、とにかく遷移がややこしい。
結構な試行錯誤を経て、以下の場合分けでよいとなる。
用語定義
t0: 初期状態または偶数回の操作後の状態
t1: 奇数回の操作後の状態
親黒: その頂点にコマが置かれていて、コマは親との間を行き来する
子黒: その頂点にコマが置かれていて、コマは子との間を行き来する
親白: その頂点にコマが置かれていない。次に親からコマが来る
子白: その頂点にコマが置かれていない。次に子からコマが来る
(t0, t1) でどの状態か？
①a: (親黒, 子黒)
①b: (親黒, 親白)
②a: (子黒, 親黒)
②b: (親白, 親黒)
③ : (子黒, 子黒)
④ : (子黒, 子白)
⑤ : (子白, 子黒)
○:白 ●:黒 ◎:どちらでもよい・不定
①a ①b ③ ④
t0 t1 t0 t1 t0 t1 t0 t1
親 ◎ ● ◎ ●
↑ ↓ ↑ ↓
● ● ● ○ ● ● ● ○
↑ ↓ ↙↖ ↗↘ ↓ ↑
子 ● ◎ ◎ ● ● ◎ ◎ ●
②a,②bは①a,①bのt0とt1を交換したもの、⑤は④のt0とt1を交換したものとなる。
奇数偶数両方の操作後ともコマがない場合というのは、よい操作が一意に決まらないので除外して考えてよい。
それぞれの遷移を考える。特に、複数の子をマージする場合に、一意に決まらなくなってしまう場合を注意する。
①a
子の中に ①a or ①b が1つ必要、ただし2つ以上あると衝突するため不可
他の子の中で、②a,②b があると明らかに衝突するため不可
他の子の中で、t1が白の頂点（④）が1つでもあると、t0からの操作が一意に決まらなくなるため不可
他の子の中で、t0が白の頂点（⑤）が1つでもあると、t1からの操作が一意に決まらなくなるため不可
よって、「1つのみ ①a or ①b を含み、他の子は③のみ」
①b
子の中で ①a,①b,②a,②b があると衝突する/状態が合わないため不可
子の中で、t0が黒の頂点（③④）が1つでもあると、その頂点にとってのt0の操作が一意に決まらなくなるため不可
よって、「子は⑤のみ」
②a
②b
③
子の中に (①a or ①b) が1つと、(②a or ②b) が1つ必要
他の子の中で、t1が白の頂点（④）が1つでもあると、t0からの操作が一意に決まらなくなるため不可
他の子の中で、t0が白の頂点（⑤）が1つでもあると、t1からの操作が一意に決まらなくなるため不可
よって、「(①a or ①b) 1つ、(②a or ②b) 1つ含み、他の子は③のみ」
④
⑤
で、上記を考えるとき、①aと①b、②aと②b の結果はくっついていても計算に問題は無いので、計算上はまとめてよい。
子をマージするときは、DPの要領で、基本は各子の③,④,⑤のパターン数を掛け合わせつつ、
「既に①を1回選んだ/まだ選んでない」などで場合分けして、1回のみ①を含むパターン数などを求めればよい。
Python3
n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
links[u].add(v)
links[v].add(u)
MOD = 998244353
# result[v] = [v1,v2,v3,v4,v5]
# v1: 奇数回目に親に移動する、部分木内のパターン数
# v2: 偶数回目に親に移動
# v3: 親には移動しないが、奇数・偶数のいずれの手順後にも駒が置かれている（異なる2つの子とのやりとり）
# v4: 初期または偶数回操作後のみ駒が置かれている
# v5: 奇数回操作後のみ駒が置かれている
result = [None for _ in range(n)]
status = [0] * n
q = [0]
while q:
u = q[-1]
if status[u] == 0:
status[u] = 1
for v in links[u]:
q.append(v)
links[v].remove(u)
else:
q.pop()
dp3_00, dp3_01, dp3_10, dp3_11, dp4_0, dp4_1, dp5_0, dp5_1 = 1, 0, 0, 0, 1, 0, 1, 0
for v in links[u]:
a1, a2, a3, a4, a5 = result[v]
ndp3_00 = dp3_00 * a3 % MOD
ndp3_01 = (dp3_00 * a1 + dp3_01 * a3) % MOD
ndp3_10 = (dp3_00 * a2 + dp3_10 * a3) % MOD
ndp3_11 = (dp3_01 * a2 + dp3_10 * a1 + dp3_11 * a3) % MOD
ndp4_0 = dp4_0 * a4 % MOD
ndp4_1 = (dp4_0 * a1 + dp4_1 * a4) % MOD
ndp5_0 = dp5_0 * a5 % MOD
ndp5_1 = (dp5_0 * a2 + dp5_1 * a5) % MOD
dp3_00, dp3_01, dp3_10, dp3_11, dp4_0, dp4_1, dp5_0, dp5_1 = \
ndp3_00, ndp3_01, ndp3_10, ndp3_11, ndp4_0, ndp4_1, ndp5_0, ndp5_1
result[u] = [(dp3_01 + dp5_0) % MOD, (dp3_10 + dp4_0) % MOD, dp3_11, dp5_1, dp4_1]
res0 = result[0]
ans = (res0[2] + res0[3] + res0[4]) % MOD
print(ans)