题解 | #红和蓝#

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)
	}
	matchIndex := 1
	match := make([]int, n+1)
	var dfs func(root int) bool
	dfs = func(root int) bool {
		mask[root] = struct{}{}
		sameColor := 0
		for _, item := range edge[root] {
			if _, ok := mask[item]; !ok {
				if !dfs(item) {
					sameColor = item
				}
			}
		}
		delete(mask, root)
		if sameColor == 0 {
			return false
		}
		match[root] = matchIndex
		match[sameColor] = matchIndex
		matchIndex++
		return true
	}
	dfs(1)
	
	success := true
	for i := 1; i <= n; i++ {
		if match[i] == 0 {
			success = false
			break
		}
	}

	var colors [100020]rune
    var dfs2 func(root int) 
	dfs2 = func(root int) {
		mask[root] = struct{}{}
		for _, item := range edge[root] {
			if _, ok := mask[item]; !ok {
				if match[item] == match[root] {
					colors[item] = colors[root]
				} else {
					colors[item] = 'R' + 'B' - colors[root]
				}
				dfs2(item)
			}
		}
	}
	colors[1] = 'R'
    dfs2(1)

    if !success {
        fmt.Println(-1)
    } else {
        fmt.Println(string(colors[1:n+1]))
    }

}