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.
It is guaranteed that the graph described in the input is a tree.
Subtask 1 [10%]
All nodes are black.
Subtask 2 [10%]
The graph is linear. More specifically, for , and .
Subtask 3 [80%]
No additional constraints.
The first line of input contains a single integer, .
The second line of input contains a string of characters, each character being either
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 a single integer, representing the number of simple paths containing at least three nodes of the same colour.
5 BBBWB 1 2 4 2 5 2 1 3
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