## DMOPC '19 Contest 3 P4 - Same Colour Leaves

View as PDF

Points: 15
Time limit: 1.4s
Java 2.0s
Memory limit: 128M

Author:
Problem type

Reina is interested in colourful trees. In particular, she currently has her eyes on a tree with nodes, each coloured either red or blue. By definition, this tree has edges, the th of which connecting nodes and . Looking at this tree, Reina wonders, "how many connected vertex-induced subgraphs of this tree form trees where all its leaves are the same colour?" Being unable to solve this problem, she has come to you for help. Since the answer may be large, she would be satisfied knowing it modulo .

#### Constraints

The degree of each node is at most .

#### Input Specification

The first line contains one integer, .
The next line contains a string with characters. The th character is R if node is red and B if it is blue.
lines follow, each one containing two space-separated integers, and , describing a bi-directional road connecting nodes and .

Note: the nodes are -indexed.

#### Output Specification

The number of subgraphs of the given tree that form trees where all its leaves are the same colour modulo .

#### Sample Input 1

6
BBRRRB
5 4
1 6
2 1
5 2
1 3

#### Sample Output 1

12

#### Explanation for Sample Output 1

There are 12 subgraphs with same coloured leaves.

#### Sample Input 2

5
BBBRB
5 3
3 2
5 1
5 4

#### Sample Output 2

11

• commented on Dec. 9, 2019, 7:58 p.m.

I really don't understand sample 1, can anyone explain it please?

• commented on Dec. 9, 2019, 9:57 p.m. edited

For sample 1, the vertices of the valid subgraphs are

(Red Leaves)

(Blue Leaves)

• commented on Dec. 10, 2019, 12:29 a.m.

Thank you!