2点間の距離(1辺の長さを1とする)が偶数なら頂点上、奇数なら辺上となる。
木の2点間距離と言えば、LCAを使ったアルゴリズムがある。
根を適当に決めて、各頂点の深さ(根からの距離)$dep[v]$ を求めておく
$c,d$ のLCAを $l_{c,d}$ とすると、$c,d$ の距離は $dep[c]+dep[d]-2dep[l_{c,d}]$
とはいえ、LCAを求めるアルゴリズムは典型ではあるがそれなりにややこしい。
今回の場合、距離そのものではなく、その偶奇がわかれば十分である。
LCAの項は2倍して使われるので、距離の偶奇は $dep[c]+dep[d]$ の偶奇と一致する。
なので、LCAは求めなくても、$dep$ を求めておくだけで、クエリには高速に答えられる。
Python3
n, qn = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
depth = [-1] * n
depth[0] = 0
q = [0]
while q:
v = q.pop()
for u in links[v]:
if depth[u] != -1:
continue
depth[u] = depth[v] + 1
q.append(u)
for _ in range(qn):
c, d = map(int, input().split())
c -= 1
d -= 1
if (depth[c] + depth[d]) % 2 == 0:
print('Town')
else:
print('Road')
しりとりは有向グラフに置き換えられるので、まずグラフを作る。
ただしその際、単語を頂点として繋げてしまうと、
「$10^5$ 個は“abc”で終わる」「$10^5$ 個は“abc”で始まる」ような入力で、辺が $10^{10}$ 本できてしまいTLE。
[aaaabc] → [abcxxx]
×
[bbbabc] → [abcyyy]
×
[cccabc] → [abczzz]
以下のように、頂点は先頭や末尾の「3文字」を表し、単語は辺にすると最大 $2 \times 10^5$ 本で済むようになる。
(aaa) (xxx)
↘ ↗
(bbb)→(abc)→(yyy)
↗ ↘
(ccc) (zzz)
その際、多重辺が生じうる点に注意する必要があるが、この問題では1本にまとめてしまってよい。
これに従ってグラフ化すると、ループしてる頂点グループや、行き止まりの頂点があったりする。
(図では3文字で無く1文字で表現する)
(a) → (b) → (c) → (d)
↑ ↓ ↓
(e) ← (f) (g) → (h)
↓ ↑
(i) → (j)
その3文字で終わる単語を言えば必ず勝てると判明した頂点を「必勝頂点」、
必ず負けると判明した単語を「必敗頂点」ということにする。
行き止まりはわかりやすく、必勝頂点である。
(a) → (b) → (c) → 勝(d)
↑ ↓ ↓
(e) ← (f) (g) → 勝(h)
↓ ↑
(i) → (j)
プレイヤーは、必勝頂点に遷移できる状態で相手にターンを渡すと、必ずそれを言われてしまう。
従って、必勝頂点に遷移できる直前の頂点は必敗頂点になる。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
(i) ─→ (j)
次に、必敗頂点にしか遷移できない頂点は、
その状態で相手にターンを回せば必ず必敗頂点に遷移してくれるので、必勝頂点である。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
(i) → 勝(j)
これを繰り返す。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
負(i) → 勝(j)
すると、どうしても決まらない頂点群が残る(注: ループならば残るわけでもない)。
必勝とも必敗とも確定しない頂点に移動し続けることができる、ということなので、
これらは「永遠に続く」頂点となる。
実装の上では、逆トポロジカルソートのようにすればよい。
準備
$R_v=\{r_1,r_2,...\}$: $v$ に流入できる頂点リスト(逆辺)
$o_v$: $v$ から出る辺の数
$ans_v$: 確定した必勝・必敗情報。最初は未確定で初期化
最初は、$o_v=0$ の頂点が行き止まりなので、それを必勝頂点にしてスタックに積む。
その後スタックが空になるまで、
ことを繰り返すとよい。最終的に未確定なら、それは永遠に続く頂点となる。
Python3
なんか、単語を頂点のまま残し、3文字を表す頂点と混在させる変な実装をしてしまっている。
n = int(input())
letters3_dict = {}
links = [set() for _ in range(3 * n)]
rev_links = [set() for _ in range(3 * n)]
out_degrees = [0] * (3 * n)
for i in range(n):
s = input()
prefix = s[:3]
if prefix in letters3_dict:
pi = letters3_dict[prefix]
else:
letters3_dict[prefix] = pi = len(letters3_dict) + n
links[pi].add(i)
rev_links[i].add(pi)
out_degrees[pi] += 1
suffix = s[-3:]
if suffix in letters3_dict:
si = letters3_dict[suffix]
else:
letters3_dict[suffix] = si = len(letters3_dict) + n
links[i].add(si)
rev_links[si].add(i)
out_degrees[i] += 1
m = len(letters3_dict)
links = links[:n + m]
rev_links = rev_links[:n + m]
out_degrees = out_degrees[:n + m]
ans = [-1] * (n + m)
q = []
for i, c in enumerate(out_degrees):
if c == 0:
q.append(i)
ans[i] = 1
while q:
v = q.pop()
# print(v, q, ans)
if v < n:
for u in rev_links[v]:
if ans[u] != -1:
continue
if ans[v] == 1:
ans[u] = 0
q.append(u)
else:
out_degrees[u] -= 1
if out_degrees[u] == 0:
ans[u] = 1
q.append(u)
continue
win = ans[v]
for u in rev_links[v]:
out_degrees[u] -= 1
ans[u] = win
q.append(u)
for a in ans[:n]:
print(['Aoki', 'Takahashi', 'Draw'][a])