Find a Root for a Three-Color Binary Tree

# Find a Root for a Three-Color Binary Tree You are given an undirected tree with nodes labeled `0` through `n - 1`, its edge list `edges`, and a string `colors`. Each node's color is `'R'`, `'B'` or `'W'`. Choose a root and orient every tree edge away from it. The rooted tree must satisfy both conditions: 1. Every node has at most two children. 2. All nodes at the same depth have the same color, and the colors advance through the repeating cycle `R -> B -> W -> R` as depth increases. The root may have any of the three colors. Thus the depth sequence may begin `R, B, W`, `B, W, R`, or `W, R, B` and repeat from there. Return the index of any valid root, or `-1` if none exists. Do not impose a smallest-label or other tie-breaking requirement. ### Function `int findColoredRoot(vector<vector<int>>& edges, string colors)` ### Example 1 **Input:** `edges = [[1, 0], [1, 2], [2, 3]], colors = "WBWR"` **One valid output:** `1` **Explanation:** With root `1`, the levels are: - Depth `0`: node `1`, colored `B`. - Depth `1`: nodes `0` and `2`, both colored `W`. - Depth `2`: node `3`, colored `R`. Node `1` has two children, node `2` has one, and the other nodes have none. The level colors follow `B -> W -> R`. ### Example 2 **Input:** `edges = [[0, 1], [0, 2], [0, 3]], colors = "RBBB"` **Output:** `-1` **Explanation:** Root `0` gives the right level colors, `R` then `B`, but has three children and violates the binary-tree property. If a leaf is the root, its color is `B` and its child, node `0`, is `R` instead of the required `W`. No root satisfies both conditions. ### Constraints - `2 <= n == colors.length <= 100000` - `edges.length == n - 1` - Each edge contains two node indices in `[0, n - 1]`. - Every character of `colors` is `'R'`, `'B'` or `'W'`. - The edges form a connected undirected tree, and every node has degree at most three. ### Clarifications - Depth is the number of edges from the chosen root; the root has depth `0`. - A child is an adjacent node one level farther from the root. Degree counts all incident edges, including a non-root node's parent edge. - Choosing a root does not change any node colors or underlying edges. - Any index meeting the stated conditions is an acceptable answer; the task does not require a canonical root choice. ### What a Strong Answer Covers - Satisfying the child-count and repeating level-color conditions together. - Allowing each of the three possible starting colors without reversing the color cycle. - Producing a valid root when one exists and establishing impossibility otherwise at the full tree-size limit.