AtCoder Regular Contest 161 C問題メモ
C - Dyed by Majority (Odd Tree)
問題
全ての頂点の次数が奇数である $N$ 頂点の木が与えられる
頂点は白か黒で塗られている
次の操作を同時に1回だけ行う
操作後の各頂点の色 $S_1,...,S_N$ が与えられるので、操作前の各頂点の色としてあり得る一例を求めよ
$T$ ケース与えられる
1つの入力につき、$N$ の総和 $\le 2 \times 10^5$
解法
操作前の色を $F_1,...,F_N$ とする。
葉は自身と親を一意に決められる
（根付き木ではないので「親」「子」というのは厳密には誤りだが、
便宜上、葉から順次処理していく過程で、先に処理された方を子→その時まだ未処理の隣接頂点を親と呼ぶ）
葉の $S_i$ が黒(白)なら、その親 $j$ の $F_j$ は黒(白)でないといけない。
S F
: :
(j) ← (j) Fj=B
| |
(i) Si=B (i)
2個以上の葉が同じ頂点に繋がり、それらの $S_i$ が矛盾すると不可能。
(j)
/ \
(B) (W) ← それぞれ Si=B、W である葉頂点
$i$ 自身の色 $F_i$ はどちらにした方がよいか？
$j$ としか関わらないので、$j$ がなるべく困らないようにしといて損しない。
つまり、$S_j$ と合わせておけばよい。
葉頂点により、「自身の色 $F_i$」と「親の色 $F_j$」が決まった。
処理した葉 $i$ は、「$j$ の隣に色が $F_i$ である頂点が1個あったよ」という情報さえ残しておけば、以降は除いて考えてよい。
葉を1つずつ処理・削除していき、新しくできた葉もまた順次処理し、
$F_i$ と $F_j$ を決めていくと、全ての頂点を決められそう。
一般化
はじめから葉であった頂点だけで無く、途中で葉になったものも含めて考える。
S
:
親 (j)
|
自分(i)
/|\＼
子 o o o o (←削除済み)
親の色
子の色が全て決まっているとすると、それらによる親の色 $F_j$ に対する要請は、以下の3ケースがあり得る。
$F_j$ に対する要請がある場合に、$j$ が、既に他の $j$ の子からも要請を受けていて、矛盾すると不可能。
一般の場合は、親の色に対する要請が無い場合もある。
つまり、次に $j$ を処理する時、$j$ 自身の色がまだ決まっていないこともある。
自身の色
自身の色 $F_i$ は、子の要請により決まっている場合はその色。
決まっていない場合（全ての子が、自身に対する要請無し）は、色はどちらでも子に対して矛盾しないので、葉の時と同様、$S_j$ に合わせておいて損しない。
よって、自身の色は少なくとも自身を処理したときに決められることがわかったので、
先ほど、親頂点の色を決める際に仮定した「子の色が全て決まっているとすると」という前提も満たされることが確認できる。
最後の1頂点
このように葉を削除していくと、最終的に1頂点残る。
(j) 最後から2頂点目 (i) の処理時のイメージ
|
(i)
最後の1頂点も、以下を確認しないといけない。
実装
みたいな2つの情報を持って、葉から処理していけばよい。
Python3
def solve(n, links, s):
leaves = [i for i in range(n) if len(links[i]) == 1]
ans = [0] * n # B:+1, W:-1
vote = [0] * n # B:+1, W:-1
sss = [1 if c == 'B' else -1 for c in s]
while leaves:
u = leaves.pop()
if not links[u]:
# ラス1
if sss[u] == 1:
if vote[u] < 0:
return False
else:
if vote[u] > 0:
return False
break
v = next(iter(links[u]))
if sss[u] == 1:
if vote[u] < 0:
return False
if vote[u] == 0:
if ans[v] == -1:
return False
ans[v] = 1
else:
if vote[u] > 0:
return False
if vote[u] == 0:
if ans[v] == 1:
return False
ans[v] = -1
if ans[u] == 0:
ans[u] = sss[v]
vote[v] += ans[u]
links[v].remove(u)
if len(links[v]) == 1:
leaves.append(v)
for i in range(n):
if ans[i] == 0:
ans[i] = 1
return ans
t = int(input())
for _ in range(t):
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)
s = input()
ans = solve(n, links, s)
if ans == False:
print(-1)
else:
ans = ''.join('B' if c == 1 else 'W' for c in ans)
print(ans)