Šarenlist
레이팅 미적용의견: 0
Warm summer night. Vito and his friend, Karlo, are lying in a forest clearing
and watching the stars. Suddenly, Vito exclaims “Karlo, look! The trees around
us are changing colors!” “Wooow so colorful” said Karlo, amazed. Indeed, the
tree branches in the forest started to change colors.
Fascinated by the colorful trees, Vito and Karlo noticed a couple of facts about
them. Each of the trees they are looking at can be represented as a tree graph,
i.e. an undirected graph in which there exists a unique path between each pair
of nodes. The trees they are looking at have the property that each edge of
the tree is colored in one of \(k\) different colors. Some of the paths on the tree
are colorful, meaning that such a path contains edges of at least two different
colors.
Morning has arrived and the tree magic is now lost. In order to relive this experience, Vito and Karlo ask
you to solve the following problem. Given a tree and \(m\) pairs of nodes on the tree, determine the number
of different colorings of the tree edges so that each of the \(m\) paths determined by the \(m\) pairs of nodes is
colorful. Since this number can be very large, output it modulo \(10^{9} + 7\).
Subtask 1 (10 points): \(m = 1\)
Subtask 2 (15 points): \(m = 2\)
Subtask 3 (10 points): Each tree edge belongs to at most one of the \(m\) given paths.
Subtask 4 (10 points): \(1 \le n \le 15\), \(k = 2\)
Subtask 5 (65 points): No additional constraints.
The first line contains three positive integers \(n\), \(m\) and \(k\) (\(3 \le n \le 60\), \(1 \le m \le 15\), \(2 \le k \le 10^{9}\)), the
number of nodes in the tree, the number of path required to be colorful and the number of possible colors
for the tree branches, respectively.
The \(i-th\) of the next \(n - 1\) lines contains a pair of positive integers \(a_{i}\) and \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le n\)), representing
an edge of the tree.
The \(j-th\) of the next \(m\) lines contains a pair of positive integers \(c_{j}\) and \(d_{j}\) (\(1 \le c_{j}\), \(d_{j} \le n\)), the labels of the
endpoints of the paths which are required to be colorful. The nodes \(c@@RISE_MATH_BLOCK_0@@j\) are not neighbouring.
In the only line print the number of ways to color the tree edges so that each of the \(m\) given paths is
colorful, modulo \(10^{9} + 7\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(m = 1\) |
2 | 15점 | \(m = 2\) |
3 | 10점 | Each tree edge belongs to at most one of the \(m\) given paths. |
4 | 10점 | \(1 \le n \le 15\), \(k = 2\) |
5 | 65점 | No additional constraints. |
3 1 2
1 2
2 3
1 324 3 2
1 2
2 3
4 2
1 4
1 3
4 304 3 3
1 2
2 3
4 2
1 4
1 3
4 36Clarification of the first example:
The tree consists of only two edges, both part of a colorful path between the nodes 1 and 3. So, the two
edges must have a different color. One such coloring is obtained by coloring the edge 1-2 in color 1, and
2-3 in color 2, while the other is obtained by switching these color so that 1-2 has color 2, and 2-3 has
color 1.
평가 및 의견
Šarenlist
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Šarenlist