You are given a connected, undirected, acyclic graph whose nodes are colored either B or W.

Find every node that can be selected as the root so that:

• The rooted graph is a valid binary tree, meaning every node has at most two children.
• All nodes at the same level have the same color.
• Adjacent levels have different colors, producing a pattern such as B, W, B, W or W, B, W, B.

As a follow-up, find the minimum number of node color changes needed so that at least one node can be selected as a valid root. Changing a node from B to W, or from W to B, costs one change.

Input Representation

• Nodes are numbered from 0 to nodeCount - 1.
• colors.charAt(nodeId) is the current color of nodeId.
• Each string in edges has the form "firstNode,secondNode" and represents an undirected edge between those nodes.

Class

AlternatingColorBinaryTree

Main Method

findValidRoots

List<Integer> findValidRoots( int nodeCount, List<String> edges, String colors)

Parameters

• nodeCount: The number of nodes in the graph.
• edges: The undirected edges encoded as "firstNode,secondNode".
• colors: A string containing the current color of every node.

Returns

Return all nodes that satisfy both the binary-tree and alternating-level color conditions when selected as the root.

Return the node identifiers in increasing order. Return an empty list if no valid root exists.

Follow-up Method

minimumColorChanges

int minimumColorChanges( int nodeCount, List<String> edges, String colors)

Parameters

• nodeCount: The number of nodes in the graph.
• edges: The undirected edges encoded as "firstNode,secondNode".
• colors: A string containing the current color of every node.

Returns

Return the minimum number of node color changes needed to make the graph satisfy the alternating-level color condition for at least one root that forms a valid binary tree.

Either color may be used for the root. Return -1 if the graph cannot form a binary tree from any root, because color changes cannot repair its structure.

Rules

• Selecting a root changes only the parent-child direction of the edges. It does not add, remove, or reorder edges.
• A node may have zero, one, or two children.
• Every node on a particular level must share one color.
• The color of every level must differ from the color of the previous level.
• Changing one node's color counts as one change.

Constraints

• 1 ≤ nodeCount ≤ 200,000
• edges.size() = nodeCount - 1
• colors.length() = nodeCount
• colors.charAt(nodeId) is either 'B' or 'W'.
• Every edge contains two different node identifiers.
• 0 ≤ firstNode, secondNode < nodeCount
• The graph is connected and contains no cycles.
• No undirected edge appears more than once.

Examples

Example 1

findValidRoots( nodeCount = 6, edges = ["0,1", "1,2", "1,3", "3,4", "3,5"], colors = "BWBBWW")

Output: [0, 2, 4, 5]

The colors already alternate across every level. Nodes 0, 2, 4, and 5 can be roots without causing any node to have more than two children.

minimumColorChanges( nodeCount = 6, edges = ["0,1", "1,2", "1,3", "3,4", "3,5"], colors = "BWBBWW")

Output: 0

No color changes are required because the current coloring already alternates correctly.

Example 2

findValidRoots( nodeCount = 5, edges = ["0,1", "1,2", "2,3", "3,4"], colors = "BBWBW")

Output: []

Every node could structurally root this path as a binary tree, but nodes 0 and 1 currently have the same color. Therefore, no root satisfies the color condition.

minimumColorChanges( nodeCount = 5, edges = ["0,1", "1,2", "2,3", "3,4"], colors = "BBWBW")

Output: 1

Changing node 0 from B to W produces "WBWBW", so one change is sufficient.

Example 3

findValidRoots( nodeCount = 5, edges = ["0,1", "0,2", "0,3", "0,4"], colors = "BWWWW")

Output: []

If node 0 is the root, it has four children. If a leaf is the root, node 0 has three children. Thus, no root forms a binary tree.

minimumColorChanges( nodeCount = 5, edges = ["0,1", "0,2", "0,3", "0,4"], colors = "BWWWW")

Output: -1

Color changes cannot make the graph structurally valid as a binary tree.