saba_tavdgiridze's blog

By saba_tavdgiridze, history, 5 years ago,

Can you give me an idea how to solve this problem ? Hotels thanks.

• 0

 » 5 years ago, # |   0 See this problem very similar .
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I have solved this problem , but I think these two are not much similar.PS maybe you're right.
 » 5 years ago, # |   +23 It can be easily shown that dist(x,y)=dist(x,z)=dist(y,z) is possible only when there exists node v, such that dist(x,v)=dist(y,v)=dist(z,v). We iterate v from 1 to n and for each we want to know the amount of good x,y,z triples. Let's delete v from the tree, then it will break down into several trees, let's denote them as T1,T2..Tk. We will run DFS for each tree T1,T2..Tk and write down pairs (depth; which_tree). Now we want to calculate the number of triples q,w,e such that q.depth=w.depth=e.depth, and q.which_tree,w.which_tree,e.which_tree are all different. Let's work with each depth separately. Considering depth D, we will write down "which_tree" values for all pairs which have .depth=D. Now, let's merge same which_tree values into one, remembering the amount. Now we're only left with the following problem: given A1,A2,A3...Az, calculate the sum of A[i]*A[j]*A[k] for all possible different i,j,k. After calculating this value for each v, just add it to the answer. And don't forget to return v back to your tree. =) Probably my code will help you to understand better: link