0 人解决，2 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
In graph theory, a tree is a connected, undirected simple graph with no cycles. A tree with n nodes always has n - 1 edges.
A path in a tree is a sequence of distinct edges which are connected (each pair of consecutive edges in the path share a vertex).
Consider a tree with n vertices and n-1 edges. You can color each edge in one of k colors.
An assignment of colors to edges is a rainbow coloring if in every path of 2 or 3 edges, the colors of the edges are different. (i.e., every two consecutive edges have different colors, and every three consecutive edges have different colors).
Given a tree and the number of colors k, find the number of rainbow colorings modulo 1000000009.
The first line of input gives the number of test cases, C(1 <= C <= 40 ). Then for each of the C cases, there will be:
For each test case, output one line. That line should contain “Case #X: Y”, where X is 1-based number of the case, and Y is the answer for that test case.
2 4 10 1 2 1 3 1 4 5 3 1 2 2 3 3 4 4 5
Case #1: 720 Case #2: 6 Hint: In the first case, the tree has four nodes. There are edges from one node to each of the other three. Each pair of these edges are adjacent, so for there to be a rainbow coloring, all the edges must have different colors. There are therefore 10 x 9 x 8 = 720 rainbow colorings. In the second case, the tree itself is a path of 4 edges, and there are 3 colors. The first three edges must all have different colors, so there are 3 x 2 x 1 colorings for these, and then there is only one choice for the fourth edge, so there are 6 rainbow colorings.
0 人解决，2 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。