I have been given a weighed undirected tree. For each subtree of this tree, I need to find the node from which the sum of distances to all other nodes in the subtree is minimum.
The no. of nodes in the tree is of the order of 10^5.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3650 |
| 2 | Benq | 3582 |
| 3 | Geothermal | 3570 |
| 3 | orzdevinwang | 3570 |
| 5 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3532 |
| 8 | Radewoosh | 3522 |
| 9 | Um_nik | 3483 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.04.2024 10:13:30 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
You want centroid of every subtree, this problem was in some CF round last year.
http://codeforces.com/contest/685/problem/B
Woukd that not be the center of the subtree?
I don't think centroid is the node from which the sum of distances to all other nodes in the subtree is minimum, atleast for a weighed tree.
Example — Consider a linear tree 1 -> 2 -> 3 -> 4 -> 5. Let edge 4 -> 5 be 100 and all other edges be 1. Then, the required node is 4 while the centroid is 3.
Cost with 4 is 100 + 1 + 2 + 3 = 106. Cost with 3 is 101 + 1 + 1 + 2 = 105.
Oh, I got confused. Thanks for the explanation.
I think the answer should literally be the centroid.
coz it is one of the properties of centroid.
Similar Problem: https://www.hackerearth.com/challenge/competitive/march-circuits-17/approximate/special-nodes/