Phân tích: Symmetric Trees

Bài toán yêu cầu xác định xem một cây có màu ở các đỉnh có thể được vẽ trên mặt phẳng 2D với một trục đối xứng hay không.

Một câu hỏi quan trọng cần đặt ra là: có bao nhiêu đỉnh trong cây nằm trên trục đối xứng? Chúng ta có thể chia thành hai trường hợp: không có đỉnh nào nằm trên trục đối xứng, và có một hoặc nhiều đỉnh nằm trên trục đối xứng.

Không có đỉnh nào trên trục đối xứng

Đây là trường hợp đơn giản hơn. Vì cây có ít nhất một đỉnh, phải có một đỉnh \(A\) ở bên trái trục đối xứng kết nối với một đỉnh \(A'\) ở bên phải trục đối xứng. Tất cả các đỉnh còn lại phải thuộc về cây con của \(A\) hoặc cây con của \(A'\). Cạnh duy nhất cắt ngang trục đối xứng là cạnh nối \(A\) và \(A'\). Không thể có thêm bất kỳ cạnh nào khác cắt ngang trục đối xứng (nếu không sẽ tạo thành chu trình). Điều kiện cuối cùng là cây con gốc \(A\) và cây con gốc \(A'\) phải đẳng cấu với nhau. Chúng ta sẽ bàn chi tiết về cách kiểm tra đẳng cấu cây sau. Hình dưới đây minh họa trường hợp này:

Có một hoặc nhiều đỉnh trên trục đối xứng

Trong trường hợp này, chúng ta có thể chọn một đỉnh \(A\) và đặt nó lên trục đối xứng. Tiếp theo, xét các con của \(A\). Mỗi con đại diện cho một cây con. Với mỗi con (hoặc cây con) của \(A\), chúng ta tìm một con khác của \(A\) đẳng cấu với nó. Nếu tìm thấy, chúng ta đặt một con bên trái và con kia bên phải trục đối xứng. Các nút gốc của các cây con không thể ghép đôi phải được đặt trên trục đối xứng. Vì chỉ có hai vị trí khả dụng trên trục (một phía trên \(A\) và một phía dưới \(A\)), số lượng con không thể ghép đôi tối đa là hai. Hai con này (nếu có) được đặt trên trục đối xứng bằng cùng một kỹ thuật, ngoại trừ việc chúng chỉ có thể có tối đa một con không ghép đôi (vì chỉ còn một vị trí khả dụng trên trục đối xứng). Xem minh họa sau:

Chúng ta ghép đôi tất cả các con của \(A\) đẳng cấu với nhau (ví dụ: \(B\) và \(B'\), \(C\) và \(C'\), v.v.) và đặt một cái bên trái, một cái bên phải trục đối xứng. Chỉ có thể còn lại tối đa hai con không ghép đôi (cây con \(X\) và cây con \(Y\)). Chúng ta có thể đệ quy đặt \(X\) và \(Y\) lên trục đối xứng ngay phía trên và phía dưới đỉnh \(A\). Cây con của \(X\) chỉ có thể có tối đa một con không ghép đôi vì chỉ còn một vị trí để đặt con không ghép đôi trên trục đối xứng (phía trên \(X\)). Tương tự với cây con của \(Y\).

Cách kiểm tra hai cây con có đẳng cấu không?

Các chiến lược đặt đỉnh trên yêu cầu một cách nhanh chóng để kiểm tra xem hai cây con có đẳng cấu hay không. Một cách để làm điều này là mã hóa mỗi cây con thành một biểu diễn chuỗi duy nhất và sau đó kiểm tra xem các chuỗi có bằng nhau không. Một cách mã hóa cây con thành chuỗi là sử dụng các dấu ngoặc lồng nhau: bắt đầu từ nút gốc của cây con, xây dựng một chuỗi bắt đầu bằng "(", tiếp theo là màu của nút, sau đó là dấu phẩy, tiếp theo là danh sách các mã hóa của các con đã được sắp xếp và ngăn cách bằng dấu phẩy, và cuối cùng là ")". Ví dụ, nếu nút \(X\) là cha của \(Y\) và \(Y\) là cha của \(Z\), mã hóa của cây con \(X\) là (X,(Y,(Z))). Nếu \(X\) là cha của \(Z\) và \(Y\), mã hóa là (X,(Y),(Z)). Lưu ý rằng mã hóa của các con phải được sắp xếp vì chúng ta muốn hai cây con có các con giống hệt nhau sẽ tạo ra cùng một chuỗi.

Dưới đây là một ví dụ cài đặt bằng Python 3:

import sys

def encode_subtree(a, parent):
  children = []
  for b in con[a]:
    if b != parent:
      if con[a][b] == -1:
        con[a][b] = encode_subtree(b, a)
      children.append(con[a][b])

  m = '(' + colors[a]
  for c in sorted(children):
    m += ',' + c
  return m + ')'


def rec_symmetric(a, parent):
  first_pair = {}
  for b in con[a]:
    if b != parent:
      if con[a][b] in first_pair:
        del first_pair[con[a][b]]
      else:
        first_pair[con[a][b]] = b

  keys = list(first_pair.values())
  if len(keys) == 0: return True

  ok = rec_symmetric(keys[0], a)
  if len(keys) == 1 or not ok: return ok

  # Non-root is only allowed one unpaired branch.
  if len(keys) > 2 or parent != -1: return False

  return rec_symmetric(keys[1], a)


def symmetric():
  # No vertex in the middle line.
  for a in range(N):
    for b in con[a]:
      if con[a][b] == con[b][a]:
        return True

  # Pick a vertex in the middle line.
  for a in range(N):
    if rec_symmetric(a, -1):
      return True

  return False


sys.setrecursionlimit(100000)
for tc in range(int(input())):
  colors = []
  con = []

  N = int(input())
  for i in range(N):
    colors.append(input())
    con.append({})

  for i in range(N - 1):
    e = input().split()
    a = int(e[0]) - 1
    b = int(e[1]) - 1
    con[a][b] = -1
    con[b][a] = -1

  for a in range(N):
    encode_subtree(a, -1)

  if symmetric():
    print("Case #%d: SYMMETRIC" % (tc + 1))
  else:
    print("Case #%d: NOT SYMMETRIC" % (tc + 1))

Dựa trên phân tích chính thức của Google Code Jam.