kth node from u to v, 0th node is u
| 33 | } |
| 34 | //kth node from u to v, 0th node is u |
| 35 | int go(int u, int v, int k) { |
| 36 | int l = lca(u, v); |
| 37 | int d = dep[u] + dep[v] - (dep[l] << 1); |
| 38 | assert(k <= d); |
| 39 | if (dep[l] + k <= dep[u]) return kth(u, k); |
| 40 | k -= dep[u] - dep[l]; |
| 41 | return kth(v, dep[v] - dep[l] - k); |
| 42 | } |
| 43 | int32_t main() { |
| 44 | int n; cin >> n; |
| 45 | for (int i = 1; i < n; i++) { |