백준 23044 트리 조각하기 (C++)

https://www.acmicpc.net/problem/23044

23044번: 트리 조각하기

bfs와 파라메트릭 서치(이분탐색)을 이용하는 문제였습니다.  폭탄을 터뜨릴 정점을 선택하는 것과 최대 거리를 둘 다 구하는것은 매우 어렵습니다. N이 20만으로 매우크기때문이죠.

따라서 우리는 둘 중 하나를 고정해서 풀어야 합니다. 이럴때 우리가 사용할 수 있는게 파라메트릭 서치입니다. 우리는 최대거리를 구하고 싶습니다. 답이 되는 최대거리+1 이후로는 당연하게도 전부 최대거리 후보가 되지 못합니다. 따라서 우리는 파라메트릭 서치를 사용할 수 있는 조건이 갖춰져있습니다.

이분탐색의 mid값이 최대거리가 될 수 있는지만 구하면 됩니다. 먼저 파괴되서는 안되는 정점들로부터 bfs를 시작하여 파괴해야하는 정점까지의 거리를 구합니다. 이를 cantgo[i]라 하겠습니다.

그리고 최대 거리값을 체크할때, 파괴해야하는 정점들 중 현재 탐색중인(파라메트릭 서치의 mid)값이 cantgo[i]보다 작다면 즉, 이 정점에 폭탄을 설치할 경우 앞서 구했던 파괴되서는 안되는 정점들로부터의 거리 cantgo[i]보다 최대거리가 크기에 설치하면 안됩니다. 

폭탄을 설치할수있는 정점들로부터 bfs를 돌리고 모든 파괴되어야하는 정점을 방문했는지 체크하면 

파라메트릭 체크함수 완성입니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int N;
vector<vector<int>> E;
bool bomb[200001];
int ans;
vector<int> cantgo;
bool chk(int a){
    bool wego[200001];
    vector<int> visit(N+1,2e9);
    queue<pair<int,int>> q2;
    for(int x=1;x<=N;x++) {
        wego[x]=false;
        if(bomb[x] && cantgo[x]>=a){
            q2.push({x,0});
            visit[x]=0;
        }
        else{
            visit[x]=2e9;
        }
    }    
    while(!q2.empty()){
        int now=q2.front().first;
        int dist=q2.front().second;
        q2.pop();
        if(dist==a) break;
        wego[now]=true;
        for(auto i : E[now]){
            if(visit[i]>dist+1 && bomb[i]){
                visit[i]=dist+1;
                q2.push({i,dist+1});
            }
        }
    }
    for(int x=1;x<=N;x++){
        if(bomb[x] && !wego[x]) return false;
    }
    return true;
}
int main(){
    cin>>N;
    queue<pair<int,int>> q;
    cantgo.push_back(0);
    for(int x=1;x<=N;x++){
        cin>>bomb[x];
        if(!bomb[x]){
            q.push({x,0});
            cantgo.push_back(0);
        }
        else cantgo.push_back(2e9);
        E.push_back(vector<int>());
    }
    E.push_back(vector<int>());
    for(int x=0;x<N-1;x++){
        int src,dst;
        cin>>src>>dst;
        E[src].push_back(dst);
        E[dst].push_back(src);
    }
    while(!q.empty()){
        int now=q.front().first;
        int dist=q.front().second;
        q.pop();
        for(auto i : E[now]){
            if(dist+1<cantgo[i]){
                cantgo[i]=dist+1;
                q.push({i,dist+1});
            }
        }
    }
    int l=1;
    int r=N;
    while(l<=r){
        int mid=(l+r)/2;
        if(chk(mid)){
            ans=max(ans,mid);
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans;
}

f