容易想到叶子节点一定要涂成蓝色,因为以叶节点为根的子树只有一个点,而0是偶数,以此类推就所有点都唯一确定。
采用深度优先搜索实现,更新当前点的所有子节点后用子节点中蓝色节点的个数来确定当前点应该是什么颜色,如果子节点中有偶数个蓝色点,则当前点为蓝色点,反之为红色。
Python代码
"小红喜欢蓝色,蓝色是永恒的象征,它是最冷的色彩,表现出一种美丽、文静、理智、安祥与洁净。 由于蓝色沉稳的特性,具有理智,准确的意象"
给你一棵n个节点的有根树,编号从 1 到 n ,根是 1 号节点。初始时,树上的每个节点都是红色。现在小红需要你构造一种"子树蓝奇"状态:这棵树的以任意一个节点为根的子树内蓝色节点的个数是奇数个。但这样的方案可太多了,所以小红要求你找到蓝色节点数最多的"子树蓝奇"状态,并输出这棵树。
第一行输入一个正整数 n 。
接下来 n−1 行,每行两个正整数 u,v ,表示 u 号节点和 u 号节点之间有一条边。
1<n<105
1≤u,v≤n
输出一个长度为 n 的字符串,表示染色后的树。如果第个字符是'R',代表树上的 i 号节点是红色;如果个字符是'B',则表示树上的第 i 号节点是蓝色。
输入
6
1 2
1 3
3 4
4 5
5 6
输出
BBRRRB