Given two weighted trees. f(x, y) — distance between x and y in the first tree, g(x, y) — distance between x and y in the second tree. How many pairs (x, y) such that x < y and f(x, y) < g(x, y). Number of vertices <= 2*10^5.
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
How to solve this magic problem?
Given two weighted trees. f(x, y) — distance between x and y in the first tree, g(x, y) — distance between x and y in the second tree. How many pairs (x, y) such that x < y and f(x, y) < g(x, y). Number of vertices <= 2*10^5.
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
ru3 | Temirulan | 2018-05-21 14:09:32 | 7 | Мелкая правка: 'x$ и $y$ в первом дереве.' -> 'x$ и $y$ во втором дереве.' | ||
ru2 | Temirulan | 2018-05-21 12:34:06 | 23 | Мелкая правка: 'le 2*10^5$.' -> 'le 2*10^5$, веса ребер $\le 10^9$.' | ||
ru1 | Temirulan | 2018-05-21 00:10:54 | 352 | Первая редакция перевода на Русский | ||
en1 | Temirulan | 2018-05-21 00:07:41 | 277 | Initial revision (published) |
Name |
---|