4
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ It's good to know the tree has $N$ vertices and $N-1$ edges. $\endgroup$ – Jorge Jun 18 '14 at 19:08
  • 1
    $\begingroup$ 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? $\endgroup$ – Perry Elliott-Iverson Jun 18 '14 at 19:21
  • 1
    $\begingroup$ @PerryIverson Please see my edit and its not any homework or programming competition $\endgroup$ – user157452 Jun 18 '14 at 19:30
  • $\begingroup$ @Bananarama Really?whats so good in it? $\endgroup$ – user157452 Jun 18 '14 at 19:35
  • $\begingroup$ every tree on $N$ vertices has $N-1$ edges. $\endgroup$ – Jorge Jun 18 '14 at 19:50
12
$\begingroup$

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)$$

$\endgroup$
4
  • $\begingroup$ @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 $\endgroup$ – user157935 Jun 19 '14 at 5:22
  • $\begingroup$ Can't you just say that triplets with good property will all belong to different trees $T_i, T_j,T_k$. $\endgroup$ – sabertooth Jun 19 '14 at 5:42
  • $\begingroup$ @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. $\endgroup$ – Perry Elliott-Iverson Jun 19 '14 at 13:12
  • $\begingroup$ @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. $\endgroup$ – Perry Elliott-Iverson Jun 19 '14 at 16:08
0
$\begingroup$
  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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.