Can you give me an idea how to solve this problem ? Hotels thanks.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
Can you give me an idea how to solve this problem ? Hotels thanks.
| Название |
|---|



See this problem very similar .
I have solved this problem , but I think these two are not much similar.PS maybe you're right.
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