DMOPC '19 Contest 3 P4 - Same Colour Leaves

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.4s

Java 2.0s

Memory limit: 128M

Author:

KevinWan

Problem type

Reina is interested in colourful trees. In particular, she currently has her eyes on a tree with $N$ ~N~ nodes, each coloured either red or blue. By definition, this tree has $N-1$ ~N-1~ edges, the $i$ ~i~th of which connecting nodes $u_i$ ~u_i~ and $v_i$ ~v_i~. 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 $10^9+7$ ~10^9+7~.

Constraints

In all subtasks,
$1 \le N \le 300\,000$ ~1 \le N \le 300\,000~
$1 \le u_i,v_i \le N$ ~1 \le u_i,v_i \le N~

Subtask 1 [10%]

$N \le 20$ ~N \le 20~

Subtask 2 [20%]

The degree of each node is at most $2$ ~2~.

Subtask 3 [30%]

$N \le 3000$ ~N \le 3000~

Subtask 4 [40%]

No additional constraints.

Input Specification

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

Note: the nodes are $1$ ~1~-indexed.

Output Specification

The number of subgraphs of the given tree that form trees where all its leaves are the same colour modulo $10^9+7$ ~10^9+7~.

Sample Input 1

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

Sample Output 1

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

Comments

3

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

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

10
Plasmatic commented on Dec. 9, 2019, 9:57 p.m. ← edited →
For sample 1, the vertices of the valid subgraphs are

(Red Leaves)

$\{3\}$ ~\{3\}~

$\{4\}$ ~\{4\}~

$\{5\}$ ~\{5\}~

$\{4, 5\}$ ~\{4, 5\}~

$\{1, 2, 3, 5\}$ ~\{1, 2, 3, 5\}~

$\{1, 2, 3, 4, 5\}$ ~\{1, 2, 3, 4, 5\}~

(Blue Leaves)

$\{1\}$ ~\{1\}~

$\{2\}$ ~\{2\}~

$\{6\}$ ~\{6\}~

$\{1, 2\}$ ~\{1, 2\}~

$\{1, 6\}$ ~\{1, 6\}~

$\{1, 2, 6\}$ ~\{1, 2, 6\}~

3

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

Thank you!