Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path from vertex a to b, vertex b to c and vertex c to a there is atleast one edge having red color.
It should be noted that (a,b,c), (b,a,c) and all such permutation will be considered as the same triplets.
EXAMPLE : Let N=5 and edges with colors are as follow :
1 2 b 2 3 r 3 4 r 4 5 b
Here answer will be 4.
EXPLANATION : (2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having read color. (2,3,5), (1,3,4) and (1,3,5) are such other triplets.
Here is my approach :
Count the triplets that don't have this property, and subtract from the total number of triplets.
If you have a path made entirely of black edges, any third node will create such a triplet, so there are N-2 such triplets.
Counting the all-black paths involves removing all red edges and measuring the resultant black sub-trees (O(N)). A black tree containing K+1 nodes contains K(K+1)/2 paths.
Once you have the number of such triplets, subtract from the number of all triplets (N(N-1)(N-2)/6), and you have your answer in O(N).
But the problem in this approch is that some triplets will be counted multiple times.So how to handle is the problem
Also N can be upto 10^5 so i want a pretty fast algorithm for it.Almost O(N) OR O(NLOGN) time..not more than it