I am trying to solve this. The graph is a tree, so I represented it as disjoint sets. To find the distance between two nodes I am finding the first common ancestor and adding the distances to reach this ancestor form the starting node and the target node. this is my code and unfortunately its giving wrong answer upon submission.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
This is an unrooted tree. Which means you don't know Fr is the parent or To is.
So how to solve the question ? I don't think we can use floyd's algorithm since the constraints are too big.
This can be solved by first change the unrooted tree to a rooted tree by simlpy pick a random node (like node 1) as the root. Then in each query just find the lowest common ancestor (lca) of two nodes in
O(log n)by using sparse table or segment tree. The distance between two nodes are(depth(Fr)-depth(lca))+(depth(To)-depth(lca)).You can have the information of finding lca in this blog http://codeforces.me/blog/entry/16221
.
Interesting logic. XD
D.collision This is a similar problem. Give it a try!!