Office Distribution

Problem Statement

Office Distribution Problem Description A country is organised as a tree of linked cities. The government wants to build exactly one office in every city, choosing from m kinds of office. To keep the kinds spread out, two cities that are one road apart or two roads apart must not receive the same kind of office. Cities that are three or more roads apart are unrestricted. Determine the number of ways to assign an office kind to every city, and return the result modulo 1000000007. The country has g_nodes cities: Cities are labelled from 1 to g_nodes . Cities are linked by g_nodes - 1 bidirectional roads. The i-th road connects the cities g_from[i] and g_to[i] . Function Description Complete the function getTotalWays in the editor below. Parameters: int m : the number of office kinds available int g_nodes : the number of cities int g_from[g_nodes - 1] : one end of each road int g_to[g_nodes - 1] : the other end of each road Returns: int : the number of ways to build the offices, modulo 10