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

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | rng_58 | 185 |

3 | Errichto | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 176 |

7 | Um_nik | 175 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 170 |

10 | -is-this-fft- | 169 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2021 15:20:13 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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