Cow At Large

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <numeric>
#include <iomanip>
using namespace std;
#define pii pair<int, int>
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const int MOD = 1e9;
const int MAX = 100005;


int n, s;
vector<int> v[MAX];
vector<int> leafs;
vector<pii> critical;
int visited[MAX];
int parent[MAX];
int dist[MAX];

void find_leaf(int cur, int par){
    if(visited[cur] == 1){
        return;
    }
    visited[cur] = 1;
    if(v[cur].size() == 1 and cur != s){
        leafs.push_back(cur);
    }
    for(auto nxt : v[cur]){
        if(nxt != par){
            find_leaf(nxt, cur);
        }
    }
}

void print_leaf(){
    cout << "Leaf: ";
    for(auto x : leafs){
        cout << x << " ";
    }
    cout << "\n";
}

void print_visited(){
    cout << "Visited: ";
    for(int i = 1; i <= n; i++){
        cout << visited[i] << " ";
    }
    cout << "\n";
}

void print_critical(){
    cout << "Critical points: ";
    for(auto x : critical){
        cout << x.second << " ";
    }
    cout << "\n";
    cout << "Critical dist: ";
    for(auto x : critical){
        cout << x.first << " ";
    }
    cout << "\n";
}

void print_parent(){
    cout << "Parent: ";
    for(int i = 1; i <= n; i++){
        cout << parent[i] << " ";
    }
    cout << "\n";
}

void find_crit(){
    memset(visited, 0, sizeof visited);
    queue<pii> pq; // cur, 1 or 2
    for(auto leaf : leafs){
        pq.push({leaf, leaf});
    }
    pq.push({s, -1});
    while(!pq.empty()){
        int cur = pq.front().first;
        int tmp = pq.front().second; // stores whether cow or farmer
        pq.pop();
        if(visited[cur] != 0){
            continue;
        }
        parent[cur] = tmp;
        if(tmp == -1){
            visited[cur] = 1;
        }
        else{
            visited[cur] = 2;
        }
        for(auto nxt : v[cur]){
            if(visited[nxt] != 0){
                continue;
            }
            else{
                pq.push({nxt, tmp});
            }
        }
    }
    pq.push({s, 0});
    while(!pq.empty()){
        int cur = pq.front().first;
        int d = pq.front().second;
        pq.pop();
        if(visited[cur] == 2){
            visited[cur] == 3;
            critical.push_back({d, cur});
            continue;
        }
        if(visited[cur] == 3){
            continue;
        }
        visited[cur] = 3;
        for(auto nxt : v[cur]){
            pq.push({nxt, d + 1});
        }
    }
    sort(critical.begin(), critical.end());
}

bool check(int x){
    memset(visited, 0, sizeof visited);
    queue<pii> pq;
    for(int i = 0; i < x; i++){
        pq.push({parent[critical[i].second], 2});
    }
    pq.push({s, 1});
    while(!pq.empty()){
        int cur = pq.front().first;
        int tmp = pq.front().second; // stores whether cow or farmer
        pq.pop();
        if(visited[cur] != 0){
            continue;
        }
        visited[cur] = tmp;
        for(auto nxt : v[cur]){
            if(visited[nxt] != 0){
                continue;
            }
            else{
                pq.push({nxt, tmp});
            }
        }
    }
    for(auto cur : leafs){
        if(visited[cur] == 1){
            // cout << "Failed: " << x << " " << cur << "\n";
            return false;
        }
    }
    return true;
}

void binary_search(){
    int lo = 1, hi = (int)critical.size();
    while(lo < hi){
        int mid = (lo + hi) / 2;
        if(!check(mid)){ // need more farmers
            lo = mid + 1;
        }
        else{
            hi = mid;
        }
    }
    cout << lo << "\n";
}


int main() {
    FAST;
    freopen("atlarge.in", "r", stdin);
    freopen("atlarge.out", "w", stdout);
    cin >> n >> s;
    for(int x, y,i = 0; i < n - 1; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    find_leaf(s, -1);
    //print_leaf();
    find_crit();
    //print_visited();
    //print_critical();
    //print_parent();
    binary_search();
}