Given any two nodes in a binary tree, find the path from 1st node to another, and tell if the path is a straight line, or there are turns on the line, find number of turns.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/15/2024 06:37:14 (j3).
Desktop version, switch to mobile version.
Supported by
u just do binary lifting, and find lca first
(u->v) = (u->lca) + (v->lca)
then u precomp d[i][j] which represenst how many turns there are when u walk 2j steps upwards
Can you explain little more?
Maybe you should read about jump pointers.
If you represent your node(it's index) by binary number, number of turns is number of adjacent pairs of different digits in that number. So, you can easily calculate number of 'turns' from root to both of them, and you could calculate that for U, V, and LCA. Then you can combine them to get a solution.