## DMPG '15 G3 - Kinako Bread 2

View as PDF

Points: 30 (partial)
Time limit: 1.8s
Memory limit: 256M

Author:
Problem types

Tohka's favorite food is kinako bread, but she likes croissants too. For dinner, Shido has bought Tohka some kinako bread and some croissants to eat, pieces in total, arranged on vertices of an undirected graph without cycles — a tree. The vertices in the tree are numbered from to . Tohka is very touched that Shido would buy her so much bread, but she is on a diet. For each of kinako bread and croissants, Tohka doesn't want to eat more than and loaves, respectively. However, the bread is so tasty that she would like to eat at least and loaves of it, respectively . Tohka has decided that she will eat all the bread on the vertices in a path between two vertices of the tree, and no more. How many ways can she choose a path of the tree to eat?

Note: A path is a sequence of unique vertices such that each pair of adjacent vertices in the path are connected by an edge in the tree. Specifically, a sequence of one vertex is considered a path.

#### Input Specification

The first line of input will have , , , , .
The second line of input will have a string representing the type of bread on each vertex from to . The character will be K if the type of bread on vertex is kinako bread or C if it's a croissant.
The next lines will contain the edges of the tree, in the format . That means there is an edge between vertex and vertex .

#### Output Specification

The output should consist of one integer on a single line, the number of ways Tohka can pick a path of the tree to eat.

#### Sample Input

10 1 2 0 2
KCCKCKKCKK
1 2
1 3
2 4
1 5
3 6
3 7
6 8
5 9
5 10

#### Sample Output

38

• commented on April 11, 2020, 2:25 p.m. edit 3

const == SpontaneousCombustion copied the code of jeffreyxiao for this problem...

Original code: https://dmoj.ca/src/150170
Offender's code: https://dmoj.ca/src/2026383

Feel free to format the offender's code to compare them better. To the offender, please refrain from copying code in the future, whatever your reasons may be. This behaviour lacks integrity and honesty, especially when you simply steal the code of another and Ctrl-R some of the key variables effortlessly. We will continue to monitor your future submissions.

Edit: The offender did not even rename variables, just removed formatting... If you believe this is a false accusation, feel free to reply and we can discuss this over Slack.

Edit 2: To respond to both replies, we know const is SpontaneousCombustion because they access DMOJ from the same IP address. Also, they submit at the exact same time, if you want to look at it from a practical standpoint. const is unlisted from excessive amounts of code copying, so his rank does not show.

Edit 3: On a side note, PeterWang, next time you copy code try to make sure it's at least in English... https://dmoj.ca/src/2024331

• commented on June 11, 2019, 2:57 p.m.

my warning is so long that the judge won't run the program :(