|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||1||1||1||100.000%|
Given a vertex-colored tree with N nodes, can it be drawn in a 2D plane with a line of symmetry?
Formally, a tree is line-symmetric if each vertex can be assigned a location in the 2D plane such that:
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line containing a single integer N, the number of vertices in the tree.
N lines then follow, each containing a single uppercase letter. The i-th line represents the color of the i-th node.
N-1 lines then follow, each line containing two integers i and j (1 ≤ i < j ≤ N). This denotes that the tree has an edge from the i-th vertex to the j-th vertex. The edges will describe a connected tree.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is "SYMMETRIC" if the tree is line-symmetric by the definition above or "NOT SYMMETRIC" if it isn't.
3 4 R G B B 1 2 2 3 2 4 4 R G B Y 1 2 2 3 2 4 12 Y B Y G R G Y Y B B B R 1 3 1 9 1 10 2 3 3 7 3 8 3 11 4 8 5 7 6 7 8 12
Case #1: SYMMETRIC Case #2: NOT SYMMETRIC Case #3: SYMMETRIC
The first case can be drawn as follows:
No arrangement of the second case has a line of symmetry:
One way of drawing the third case with a symmetry line is as follows: