| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
You are given a tree. Each node has a value. You need to choose three distinct paths in the tree. Let's suppose that
P1= sum of path 1, p2 = sum of path 2, P3 = sum of path 3
Print minimum and maximum possible value of
|P1-P2| + |P2-P3| + |P3-P1|
Constraints 3<= n <= 2e5
I'm sorry, I'm not qualified to solve this easy of a problem. Please show me how to solve it.
I'd say that because we compare all 3 paths, that we can assume that P1 >= P2 >= P3. Now if we work out the absolute values we get P1 — P2 + P2 — P3 + P1 — P3 = 2*P1 — 2*P3.
In order to solve this, we need to "block" each edge (one at a time, this edge is the path with minimum sum) and find the maximum path in the 2 created trees. With DP this should be doable in O(n). As for path number 2 I guess it's allowed to have an empty path?
Or if it's not, we can then use an unused edge in the trees for that path or take one greedily from the maximum sum one (with an extra check for both ones)
p1 is maximum sum path, and p3 is minimum, which means we can take any other path since its sum will always be less than p1 and greater than p3 (or equal)
Will this work for minimum possible value?
It won't work for the minimum possible value, and I still have no idea how to properly do it. I will let you know if I have an idea
I just cant wrap my head around how you made the P2 just disappear into thin air.
If your approach is indeed correct, Maths make me feel WTF
The most important part is that we compare each pair of paths (you can check it easily for all possibilities, for example take P2 >= P1 >= P3). And when you work out the absolute values (which is possible since we now know the relative sums of the paths).
Also when we do the second part, it should be clear that when we take the minimum edge for P3 that this will remain the minimum. Now to see that P2 can't be bigger than P1: Let's say that there is an edge left with a weight C. Now, if this edge is bigger than P1, then we didn't take the maximum path for P1 and thus this is a contradiction, so P2 will indeed be smaller ( or equal, but that's ok).
In many problems where you want to minimize or maximize a certain equation this "technique" is used to reduce the problem to easier subproblems.