Build Monuments

Problem Overview

• Compute the number of ways to assign one of monumentTypes to each city so that adjacent cities and cities sharing a neighbor never have the same type.
• Input: totalCities (nodes), routeStart/routeEnd (tree edges), monumentTypes; Output: count of valid configurations modulo 1e9+7.
• Context: Coderland’s road network forms a tree; each city must host exactly one monument.
• This graph-coloring problem is a classic coding interview problem and interview question for trees with distance-2 constraints.