Colored Tree

general
1

Given a tree of size n(\leq 10^5) with each vertex colored either black or white. Find the number of paths with alternating colors.

Input: First line will have n, the number of vertices of the tree and then n-1 lines will follow of the form u v which denote an edge between the vertex u and v. Finally, the next line will contain the space separated color(either W for white or B for Black) of each vertex.
Output: Single number denoting the number of paths with alternating colors.

Sample Input
3
1 2
1 3
W B B
Sample Output
6

Explanation:
[1],[2],[3],[1,2],[1,3],[1,2,3]

2

Let dp[i] = number of alternating colored paths where i is the topmost node
for leafnodes , dp[i] = 1
for nonleaf nodes , dp[i] = 1 + dp[child] where child is of opposite color of node for nodes start at i + sum of dp[child1] * dp[child2] for paths whose lca is node , this can be reduced to O(n) with combinatorix
ans is sum of all dp[i]

3

easy but nice problem (y)

4

Nice question, I suggest if we give updates to make it tougher.
I think it might be solvable by hld, although this question would look similar to the QTREE series of SPOJ