In a weighted tree, how to find for every node the distance to its farthest node (in linear time)?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Название |
---|
Now for each node the maximum distance is the maximum of the distances calculated in steps 2 and 3.
Could you please explain the 3rd step a little bit more? I didn't understand the thing about second longest distance :( I was trying to solve IOI 2013 Dreaming... This thing is needed there :)
This was the main idea to solve problem dreaming in IOI 2013 , but the official solution is not published I don't know why. however ,the idea as pllk said
Another interesting solution:
Start at an arbitrary node, and find the node farthest from it. Then, find the node farthest from that node. This distance is the diameter of the tree (largest distance between two nodes).
First find the tree diameter using the algorithm given by aquamongoose and keep also the diameter nodes d1 and d2 (the tips). Then for all the nodes in the tree, the farthest node is either d1 or d2, (suppose that this is not the case, then you have a path that is longer than the diameter which is a contradiction, I hope you can derive the proof from this hint), then you just need to calculate the distance to d1 and d2 and pick the farthest, you can implement a (linear) LCA for this purpose or use the off-line Tarjan algorithm. The weights should be non-negative for this to work.
About last step: you don't have to use LCA, as distance from two offline-known vertexes can be found using a simple DFS ;-)
You are right, you can just calculate all the distances from d1 using a DFS and the same for d2, anything else would be an overkill.
Can you please elaborate more the proof? I don't understand why "suppose that this is not the case, then you have a path that is longer than the diameter which is a contradiction"
Can you give a link to that problem? (If it's somewhere on some online judge)
http://acm.sgu.ru/problem.php?contest=0&problem=134
updated link