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 .

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [30%]

All of the bread will be kinako bread.

##### Subtask 3 [40%]

#### 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`

## Comments

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

Problem:https://dmoj.ca/problem/apio10p1 Original:https://dmoj.ca/src/1966198 Copied:https://dmoj.ca/src/1977623

Problem:https://dmoj.ca/problem/coci14c7p5 Original:https://dmoj.ca/src/1564485 Copied:https://dmoj.ca/src/1944895

Problem:https://dmoj.ca/problem/ccc19s4 Original:https://dmoj.ca/src/1830996 Copied:https://dmoj.ca/src/1843794

To be fair it could just be similar code

Everyone copying bruce lol

Problem: https://dmoj.ca/problem/joi14p1 Original: https://dmoj.ca/src/2026536 Copied: https://dmoj.ca/src/2026536 Copied: https://dmoj.ca/src/2026565 Copied: https://dmoj.ca/src/2026528

how do you really know the difference between copied and similar. for some problems almost everyones code looks same

it's easier for more complex problems

It's also obvious if you suddenly start submitting to problems which are well beyond your skill level...

Hmmmm... Looks familiar...

it might be just that bruce is testing for them

This comment is hidden due to too much negative feedback. Click here to view it.

Do you not realize there are services known as VPNs that change your public IP? Anyways, check your Slack for proof. Also, if you just check all const recent submissions, you will see that most of them coincide exactly with SpontaneousCombustion submission times. If that's not enough evidence, I don't know what is.

Edit: Literally all 5 of const solved problems are submitted at the same time as SpontaneousCombustion. Please actually check before you make false claims.

This comment is hidden due to too much negative feedback. Click here to view it.

Why does const not have rank by points on his profile?

It happens when you're unlisted from the points leaderboard, usually because you copied others' code for points.

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