Bad Bunnies

    1#include <bits/stdc++.h>
    2using namespace std;
    3int main(){
    4    ios::sync_with_stdio(0);
    5    cin.tie(0);
    6    int n, r; cin >> n >> r;
    7    vector<vector<int>> adj(n + 1);
    8    for (int i = 0; i < n - 1; i++){
    9        int u, v; cin >> u >> v;
    10        adj[u].push_back(v);
    11        adj[v].push_back(u);
    12    }
    13    vector<int> distRabbit(n + 1, INT_MAX);
    14    queue<int> q;
    15    for (int i = 0; i < r; i++){
    16        int r; cin >> r;
    17        distRabbit[r] = 0;
    18        q.push(r);
    19    }
    20    int s, t; 
    21    cin >> s >> t;
    22    while (!q.empty()){
    23        int u = q.front(); q.pop();
    24        for (int v : adj[u]) {
    25            if (distRabbit[v] == INT_MAX) {
    26                distRabbit[v] = distRabbit[u] + 1;
    27                q.push(v);
    28            }
    29        }
    30    }
    31 
    32    //from s to get parent to reconstruct from s to t path
    33    vector<int> parent(n + 1, -1);
    34    queue<int> q2;
    35    parent[s] = s;
    36    q2.push(s);
    37    while (!q2.empty() && parent[t] == -1){
    38        int u = q2.front(); q2.pop();
    39        for (int v : adj[u]){
    40            if (parent[v] == -1){
    41                parent[v] = u;
    42                q2.push(v);
    43            }
    44        }
    45    }
    46    // reconstruct path from t to s
    47    int ans = INT_MAX;
    48    for (int cur = t; ; cur = parent[cur]){
    49        ans = min(ans, distRabbit[cur]);
    50        if (cur == s) break;
    51    }
    52    cout << ans << '\n';
    53    return 0;
    54}
    55