We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
2.)count number of nodes in each trees formed after removing red edges.
3.) Let {T1,T2,…,Tm} be the maximal subtrees with all black edges, and suppose these trees have t1,t2,…,tm vertices, respectively. For each Ti, the number of bad triplets with all three vertices among V(Ti) is C(ti,3). The number of bad triplets having two vertices among V(Ti), and one vertex among the remaining vertices is C(ti,2)(N−ti)
. All bad triplets are of one of these forms. So we have that the number of good triplets is:
answer=(C(N,3)−(for i=1 to m)∑(C(ti,3)+C(ti,2)(N−ti)))%1000000007
Kundu and Tree
You are viewing a single comment's thread. Return to all comments →
1.)Remove all red edges.
2.)count number of nodes in each trees formed after removing red edges.
3.) Let {T1,T2,…,Tm} be the maximal subtrees with all black edges, and suppose these trees have t1,t2,…,tm vertices, respectively. For each Ti, the number of bad triplets with all three vertices among V(Ti) is C(ti,3). The number of bad triplets having two vertices among V(Ti), and one vertex among the remaining vertices is C(ti,2)(N−ti)
. All bad triplets are of one of these forms. So we have that the number of good triplets is:
answer=(C(N,3)−(for i=1 to m)∑(C(ti,3)+C(ti,2)(N−ti)))%1000000007