AtCoder Regular Contest 161 C問題メモ

AtCoder Regular Contest 161

Dまでは、証明は難しいけど発想は得やすい問題が多かった印象。

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ケースがあり得る。

$S_i$ と同じ色の方が多い → $F_j$ は何でもいい
同数である → $F_j$ は $S_i$ と同じ色でないといけない
- 葉の場合は、子が無いので自然とこれになっていた
$S_i$ と異なる色の方が多い → 不可能決定

$F_j$ に対する要請がある場合に、 $j$ が、既に他の $j$ の子からも要請を受けていて、矛盾すると不可能。

一般の場合は、親の色に対する要請が無い場合もある。
つまり、次に $j$ を処理する時、 $j$ 自身の色がまだ決まっていないこともある。

自身の色

自身の色 $F_i$ は、子の要請により決まっている場合はその色。
決まっていない場合（全ての子が、自身に対する要請無し）は、色はどちらでも子に対して矛盾しないので、葉の時と同様、 $S_j$ に合わせておいて損しない。

よって、自身の色は少なくとも自身を処理したときに決められることがわかったので、先ほど、親頂点の色を決める際に仮定した「子の色が全て決まっているとすると」という前提も満たされることが確認できる。

最後の1頂点

このように葉を削除していくと、最終的に1頂点残る。

(j)  最後から2頂点目 (i) の処理時のイメージ
 |
(i)

最後の1頂点も、以下を確認しないといけない。

自身の色 $F_j$ を決定
- 決まっていればよし
- 決まっていなければ、親に対する要請がどの子からも無い状態なので、黒白好きな方を $F_j$ としてよい
全ての子の色が決まっているので、それが $S_j$ と矛盾しないか

実装

color[i]: $F_i$ が、0:未確定、1:黒確定、-1:白確定
vote[i]: $i$ の子が処理されるたびに、黒1頂点ごとに $+1$ 、白1頂点毎に $-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)

            

        
      