Hi guys, I've encountered an interesting problem. We are given a tree with N vertices and with its edges. All edges are with length 1 and we need to find for every edge the sum of the lengths of all paths in the tree that go through this edge. As you probably assume N can be large so N^2 is not good enough.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 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- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.04.2024 18:13:45 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
http://discuss.codechef.com/questions/6446/testers-editorial
This is a generalized version of your problem.
Requested value is equal to the sum of paths legnths on the one side of edge (from vertex of this edge to all other vertexes on this side of edge) times the amount of vertexes on the other side, plus vise versa product, and plus product of amounts of vertexes of both sides of edge. Both these values (sum of legnths of all paths and numver of vertexes) it is easy to find with help of dymanic programming on the tree.
OK, so i have this test:
Can you show me about edge 1-2 because I can't figure it out...The answer is 13 but I can't get that result with your formula
Why?
First side (around vertex 1): 2 vertexes (1, 5), only path 1-5, sum of lenth: 1.
Second side (around vertex 2): 3 vertexes (2, 3, 4), two paths: 2-3, 2-4, sum of length: 2.
1*3 + 2*2 + 2*3 = 13.
Yes, thank you! I just figured it out myself. Thank you anyways! Now I need to think out the dp table for the sum of lengths and everything is good.
When you calculate sum of length of some vertex, for each its child add value (sum of lengths of paths from this child)+(amount of descendents of this child, including this child), because you have all same paths but each one edge longer.
Yeah but if this vertex is in another edge that sum would be different and I can't afford to launch too many searches
You mean this problem 294E - Shaass the Great?
Edit: just realize this one is much harder.