## Yet Another Contest 1 P2 - A Boring Problem

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M
Java 512M
Python 512M

Authors:
Problem types

You are given a tree containing nodes where each node is coloured black or white. The -th edge is bidirectional and connects the nodes and . Find the number of simple paths containing at least three nodes of the same colour.

Note that traversing a path from either end counts as the same path.

#### Constraints

It is guaranteed that the graph described in the input is a tree.

All nodes are black.

The graph is linear. More specifically, for , and .

#### Input Specification

The first line of input contains a single integer, .

The second line of input contains a string of characters, each character being either B or W. The -th node is black if the -th character is B, and white otherwise.

The following lines of input contain two space-separated integers and , representing that there is a bidirectional edge between and in the tree.

#### Output Specification

Output a single integer, representing the number of simple paths containing at least three nodes of the same colour.

#### Sample Input

5
BBBWB
1 2
4 2
5 2
1 3

#### Sample Output

4

#### Explanation

The simple paths in the graph with at least three nodes of the same colour are the paths between nodes:

• 1 and 5
• 2 and 3
• 3 and 4
• 3 and 5