题解 | #红和蓝#

package main

import (
	"fmt"
)

func main() {
	var n int
	var edge = make(map[int][]int, 0)
	mask := make(map[int]struct{})
	fmt.Scan(&n)
	for i := 1; i < n; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		edge[a] = append(edge[a], b)
		edge[b] = append(edge[b], a)
	}
	dp := make([][]int, 400040)
	// 0 第一个红
	// 1 第二个红
	// 2 第一个蓝
	// 3 第二个蓝
	// dp[1<<2+0] = -1
	// dp[1<<2+2] = -1
	var dfs func(root int)
	dfs = func(root int) {
		mask[root] = struct{}{}
		if (root == 1 && len(edge[root]) > 0) || (root != 1 && len(edge[root]) > 1) {
			for _, item := range edge[root] {
				if _, ok := mask[item]; ok {
					continue
				}
				dfs(item)
			}

			mark1, mark2, mark3, mark4 := true, true, true, true
			list := make([]int, 0, len(edge[root]))
			// 假定当前为第一个红
			for _, item := range edge[root] {
				if _, ok := mask[item]; ok {
					continue
				}
				if len(dp[item<<2+3]) == 0 {
					mark1 = false
					break
				}
				list = append(list, item<<2+3)
			}
			if mark1 {
                dp[root<<2] = list
			}
			list = make([]int, 0, len(edge[root]))

			// 假定当前为第二个红 TODO
			// 查找第一个红
			red := 0
			for _, item := range edge[root] {
				if _, ok := mask[item]; ok {
					continue
				}
				if len(dp[item<<2+3]) == 0 {
					if red == 0 && len(dp[item<<2]) != 0 {
						red = item << 2
						list = append(list, item<<2)
						continue
					}
					mark2 = false
					break
				}
				list = append(list, item<<2+3)
			}
			if mark2 {
				if red == 0 {
					for _, item := range edge[root] {
						if _, ok := mask[item]; ok {
							continue
						}
						if len(dp[item<<2]) != 0 {
							list[len(list)-1] = item << 2
							dp[root<<2+1] = list
							break
						}
					}
				} else {
					dp[root<<2+1] = list
				}
			}
			list = make([]int, 0, len(edge[root]))

			// 假定当前为第1个蓝
			for _, item := range edge[root] {
				if _, ok := mask[item]; ok {
					continue
				}
				if len(dp[item<<2+1]) == 0 {
					mark3 = false
					break
				}
				list = append(list, item<<2+1)
			}
			if mark3 {
				dp[root<<2+2] = list
			}
			list = list[:0]

			// 假定当前为第二个蓝
			// 查找第一个蓝
			blue := 0
			for _, item := range edge[root] {
				if _, ok := mask[item]; ok {
					continue
				}
				if len(dp[item<<2+1]) == 0 {
					if blue == 0 && len(dp[item<<2+2]) != 0 {
						blue = item<<2 + 2
						list = append(list, item<<2+2)
						continue
					}
					mark4 = false
					break
				}
				list = append(list, item<<2+1)
			}
			if mark4 {
				if blue == 0 {
					for _, item := range edge[root] {
						if _, ok := mask[item]; ok {
							continue
						}
						if len(dp[item<<2+2]) != 0 {
							list[len(list)-1] = item<<2 + 2
							dp[root<<2+3] = list
							break
						}
					}
				} else {
					dp[root<<2+3] = list
				}
			}
			
		} else {
			dp[root<<2+0] = []int{-1}
			dp[root<<2+2] = []int{-1}
		}
		delete(mask, root)
	}
	dfs(1)

	var runes [100020]rune
    ans := false
	if !ans && len(dp[1<<2+1]) != 0 {
        ans = true
		runes[1] = 'R'
		queue := append([]int{}, 1<<2+1)
		for len(queue) != 0 {
			root := queue[0]
			queue = queue[1:]
			for _, item := range dp[root] {
				if item == -1 {
					continue
				}
				if item%4 < 2 {
					runes[item>>2] = 'R'
				} else {
					runes[item>>2] = 'B'
				}
				queue = append(queue, item)
			}
		}
	}

	if !ans && len(dp[1<<2+3]) != 0 {
		runes[1] = 'B'
		queue := append([]int{}, 1<<2+3)
		for len(queue) != 0 {
			root := queue[0]
			queue = queue[1:]
			for _, item := range dp[root] {
				if item == -1 {
					continue
				}
				if item%4 < 2 {
					runes[item>>2] = 'R'
				} else {
					runes[item>>2] = 'B'
				}
				queue = append(queue, item)
			}
		}
	}
    
    if !ans {
        fmt.Println(-1)
    } else {
        fmt.Println(string(runes[1:n+1]))
    }

}