DMOPC '19 Contest 3 P4 - Same Colour Leaves

View as PDF

Submit solution

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 N nodes, each coloured either red or blue. By definition, this tree has N-1 edges, the ith of which connecting nodes u_i and 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.

Constraints

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

Subtask 1 [10%]

N \le 20

Subtask 2 [20%]

The degree of each node is at most 2.

Subtask 3 [30%]

N \le 3000

Subtask 4 [40%]

No additional constraints.

Input Specification

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

Note: the nodes are 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.

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

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\}
      • \{4\}
      • \{5\}
      • \{4, 5\}
      • \{1, 2, 3, 5\}
      • \{1, 2, 3, 4, 5\}

      (Blue Leaves)

      • \{1\}
      • \{2\}
      • \{6\}
      • \{1, 2\}
      • \{1, 6\}
      • \{1, 2, 6\}

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

        Thank you!