# Counting triplets with red edges in each pair

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

• It's good to know the tree has $N$ vertices and $N-1$ edges. – Jorge Jun 18 '14 at 19:08
• Is there a question here? You should give some more context. Are you looking for any algorithm for this? The most efficient algorithm? Is this for a programming competition? Homework? Personal interest? – Perry Elliott-Iverson Jun 18 '14 at 19:21
• @PerryIverson Please see my edit and its not any homework or programming competition – user157452 Jun 18 '14 at 19:30
• @Bananarama Really?whats so good in it? – user157452 Jun 18 '14 at 19:35
• every tree on $N$ vertices has $N-1$ edges. – Jorge Jun 18 '14 at 19:50

## 2 Answers

Let's call triplets having your property good triplets, and those that don't bad. Let's count the bad triplets. Let $\{T_1, T_2, \dots, T_m\}$ be the maximal subtrees with all black edges, and suppose these trees have $t_1, t_2, \dots, t_m$ vertices, respectively. For each $T_i$, the number of bad triplets with all three vertices among $V(T_i)$ is $\binom{t_i}{3}$. The number of bad triplets having two vertices among $V(T_i)$, and one vertex among the remaining vertices is $\binom{t_i}{2}(N - t_i)$. All bad triplets are of one of these forms. So we have that the number of good triplets is:

$$\binom{N}{3} - \sum_{i=1}^{m} \left(\binom{t_i}{3} + \binom{t_i}{2}(N - t_i) \right)$$ $$=\frac{N(N-1)(N-2)}{6} - \sum_{i=1}^{m} \left(\frac{t_i(t_i-1)(t_i-2)}{6} + \frac{t_i(t_i-1)}{2}(N - t_i) \right)$$ $$=\frac{1}{6}\left(N(N-1)(N-2) - \sum_{i=1}^{m} t_i(t_i-1)(3N-2t_i-2)\right)$$

• @PerryIverson Please see my edit and its not any homework or programming competition – user157452 9 hours ago hackerrank.com/contests/w5/challenges/kundu-and-tree – user157935 Jun 19 '14 at 5:22
• Can't you just say that triplets with good property will all belong to different trees $T_i, T_j,T_k$. – sabertooth Jun 19 '14 at 5:42
• @sabertooth That's a good point. However you can calculate the formula I presented in $O(m)$ time, while calculating $\sum_{i=1}^{m-2} \sum_{j=i+1}^{m-1} \sum_{k=j+1}^{m} t_i t_j t_k$ will take $O(m^3)$ time. – Perry Elliott-Iverson Jun 19 '14 at 13:12
• @zack You made a comment in a suggested edit that the formula here is incorrect, based on a path with 4 edges: v1-r-v2-b-v3-b-v4-r-v5. The formula gives 3, and you say it should be 2. My understanding is that the vertex sets {v1,v2,v5}, {v1,v3,v5}, and {v1,v4,v5} should all be good sets. – Perry Elliott-Iverson Jun 19 '14 at 16:08
1. Using depth-first search, create an array containing the sizes of connected components connected only by black edges in $$\Theta(n)$$ time and $$\Theta(n)$$ space.
2. Using the array, count the total number of triplets as the sum of product of all triplets in the array.

The last step can be done by dynamic programming in $$\Theta(m)$$ time and $$\Theta(1)$$ space (if the array of sizes is of size $$m$$).

• Let $$s[k]$$ be the sum of all combinations of $$k$$ elements in an array. If an item $$x$$ is added to array, the new value of $$s[k]'$$ is $$s[k] + s[k-1] * x$$ for $$k>0$$ with $$s[0]=1$$ for convenience.
• Start with $$s[k]=0$$ for $$k>0$$ and add each item from A.
• The answer is $$s[3]$$ after all elements have been added.