Hi how to solve this question.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.04.2026 02:26:24 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Let X and Y is the beginning and the end of one of the longest paths in the tree. Longest possible path length from any vetex z is equal to maximal distance between z and x, and between z and y. To find distance between pairs of vertices you can find their LCA(Least Common Ancestor) in Log(n).
you have to find the longest path which is called as the diameter of the tree. Let us suppose U and V are the pair of vertices such that U->V is one diameter of the tree. Now it is gurantee that the longest path from any node X will be the maximum of the two paths
From X to U
From X to V
You can do 2 times DFS once from the vertex U and other from the vertex V , side by side maintaining distance from both vertices ... This way you can solve this problem without the knowledge of LCA and the time complexity of this solution is O(V+E)
Another way to solve this problem is straightforward DP on a tree.
First of all we have to find Down[i] — length of longest path starting from vertex i and going down. To find it you need to pick best value among sons of given vertex, this part can be implemented with a single DFS.
After that we can find Up[i] — length of longest path starting from vertex i and going up. Here you have 2 possibilities. Let's say that j is a parent of i. Then Up[i] may be either Up[j]+1, if we'll move up from j, or Down[q]+2, where q is some other son of j, if we'll choose to move down from j instead of moving up. This part of solution also can be implemented with a single DFS.
And now it is clear that answer for every vertex is max(Down[i],Up[i]).