(int a, int b)
| 172 | } |
| 173 | |
| 174 | public static int getLca(int a, int b) { |
| 175 | while (top[a] != top[b]) { |
| 176 | if (dep[top[a]] <= dep[top[b]]) { |
| 177 | b = fa[top[b]]; |
| 178 | } else { |
| 179 | a = fa[top[a]]; |
| 180 | } |
| 181 | } |
| 182 | return dep[a] <= dep[b] ? a : b; |
| 183 | } |
| 184 | |
| 185 | public static int getDist(int x, int y) { |
| 186 | return dep[x] + dep[y] - (dep[getLca(x, y)] << 1); |