2025 KOI 고등부 1차 대회 3번(택배 운송) 풀이

이미지를 누르면 문제로 이동합니다

 

이 문제는 노드 간 거리가 정해진 트리가 있을 때, 각 트리의 노드에서 거리 d만큼을 선택하거나 취소할 수 있는 쿼리가 주어진다.

이때 쿼리마다 1번 노드에서 N번 노드까지 모두 선택되어 있는지를 쿼리마다 출력하는 문제이다.

Q개의 쿼리에서 1 A B 가 들어오면 A에서 B만큼의 거리가 선택되는 것이고, 2 C 가 주어지면 C번째 시나리오(선택 쿼리)가 선택 해제가 된다.

이 트리는 문제의 예제를 나타낸 것이다. 그 다음에 쿼리를 하나씩 진행해 보자.

1번 쿼리

2번 쿼리

이렇게 계속 진행해 보자.

5번 쿼리

5번 쿼리까지 진행한 모습이다. 아직 1에서 11까지 도달하지 못했기 때문에 NO를 출력한다.

그럼 이제 6번 쿼리를 해보자. 

6번 쿼리

 

6번 쿼리까지 진행하면 1부터 11까지 모두 선택이 가능하기 때문에 YES를 출력한다. 이후 7,8,9 번 쿼리까지 진행해도 1부터 11까지 모두 연결되기 때문에 YES 를 출력한다.

10,11번 쿼리는 2C로 C번째 시나리오를 빼는 쿼리인데, 10번째 쿼리인 2 7의 경우,

7번째 시나리오인 1 9 6을 빼주면 된다. 7번째 시나리오를 제외해 줘도 1부터 11까지 가는 데에는 문제가 없기 때문에 YEs를 출력한다.

마지막으로 11번 쿼리인 2 1의 경우, 1번째 시나리오인 1 1 4를 빼줘야 되는데, 이 경우 1번과 3번 사이에서 빈칸이 생기기 때문에 NO를 출력한다.

 

그럼 이걸 어떻게 풀 수 있을까?

우린 여기서 탐색해야 될 구간이 정해져 있음을 주목해야 한다.

문제에선 1번부터 11번까지의 거리에 대해 묻고 있기 때문에 1부터 11을 한 줄로 정렬시켜 보자.

 

1부터 N인 11까지를 일렬로 나열하고, 나열된 노드에 맞게 연결해 주면 위와 같이 나타난다. 

이 트리에서 각 점들이 1 -> 11 구간에서 가장 먼저 만나는 점을 찾아보자.

2는 3,7과 8은 4, 6,9,10 은 5가 가장 가까운 점이 된다.

 

여기서 다시 생각해 봐야 될 점이 "가장 가까운 점은 어떻게 구할 수 있는가"인데,

이는 LCA와 이분탐색을 이용해서 구할 수 있다.

일단 트리의 루트노드를 1로 두고 LCA에 필요한 sparse table을 만들어 준다.

1 -> 11 구간에서의 점들을 나열해 보자. 위 그림에선 1, 3, 4, 5, 11가 된다.(정렬한 순서가 아닌, 이동 순서이다.)

여기서 중앙 점과 쿼리의 시작점과의 LCA를 비교한다. 예를 들어 9가 쿼리의 시작점이라면, 4과 9의 LCA 를 구한다.

LCA(4,9)는 4인데, 이렇게 LCA 값과 mid 값이 같을 경우 right = mid로 업데이트 하고, 값이 다를 경우 left = mid+1로 업데이트 한다. 이렇게 하는 이유는 가장 가까운 노드를 찾기 위한 과정에서 LCA 와 mid 가 같다면 그 점이 가장 가까운 점의 후보가 된다. 그러므로 right = mid 로 두고, 같지 않다면 mid+1 ~ right 구간에서 가장 가까운 점이 있다는 것이 되므로, right = mid+1 로 둔다.

이렇게 이분탐색을 진행하면 1 -> 11 구간에서 가장 가까운 점을 구할 수 있다.

 

이렇게 가장 가까운 점을 안다면 그 점과의 거리도 구할 수 있다.

 

우리가 결국 탐색해야 되는 구간은 1 -> 11 구간이기 때문에 이 구간에 해당되지 않는 점에서 쿼리가 주어진다면 그 점으로부터 1 -> 11 사이의 구간에 얼마나 영향을 미치는지만 알면 된다.

즉 얼마만큼의 구간을 차지하는지를 알면 되는데, 우리는 앞서 1 -> 11 구간에서 가장 가까운 점을 구했으니 그 점까지의 거리를 제외한 나머지 거리를 가장 가까운 점을 기준으로 좌우에 업데이트해주면 된다.

예를 들어 1 7 10이라는 쿼리가 주어진다면, 7번에서 가장 가까운 4번까지의 거리인 2를 빼주고, 나머지 8만큼을 4에서 좌우로 더해주면 된다.

이렇게 쿼리를 계속 진행한다면 답을 구할 수 있는데, 한 가지 문제는 이 문제에서 제공하는 거리의 값은 최대 10^9라는 점이다.

하지만 이를 해결하는 방법은 간단하다.

 

우리의 입력을 통해 만들어질 수 있는 구간은 최대 Q개, 그리고 각 Q당 좌우 범위에 해당되는 점 2개가 만들어지기 때문에 최대 2Q개의 점을 이용한다. 즉 10^9 이상의 값들을 모두 이용할 필요 없이 2Q개만 이용하면 되기 때문에 좌표압축을 이용해서 구간을 잡으면 된다.

 

 이제 우리는 문제를 풀기 위한 모든 방법들을 알았다.

LCA와 좌표 압축, 그리고 구간 업데이트를 할 수 있는 느리게 갱신되는 세그먼트 트리(세그레이지)를 이용하면 이 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,u,v,w;
struct nd{
    ll v,w;
};
ll MAX=20;
vector<nd>graph[200010];
ll parent[200010][20];
ll vis[200010];
ll depth[200010];
ll lengths[200010];
struct nc{
    ll n,c;
};
vector<nc>path;
ll fd(ll x,ll pr){
    for(int i=0;i<graph[x].size();i++){
        nd nt=graph[x][i];
        if(nt.v==pr)continue;
        ll T=fd(nt.v,x);
        if(T){
            path.push_back({x,nt.w});
            return 1;
        }
    }
    if(x==n)return 1;
    return 0;
}
ll wide[200010];
void dfs(ll x,ll pr){
    vis[x]=1;
    for(int i=0;i<graph[x].size();i++){
        nd nt=graph[x][i];
        if(vis[nt.v])continue;
        lengths[nt.v]=lengths[x]+nt.w;
        parent[nt.v][0]=x;
        depth[nt.v]=depth[x]+1;
        dfs(nt.v,x);
    }
}
ll LCA(ll u,ll v){
    if(depth[u]<depth[v])swap(u,v);
    ll diff=depth[u]-depth[v];
    ll cnt=0;
    while(diff>0){
        if(diff%2)u=parent[u][cnt];
        diff/=2;
        cnt++;
    }
    if(u!=v){
        for(int i=MAX-1;i>=0;i--){
            if(parent[u][i]!=-1 && parent[u][i]!=parent[v][i]){
                u=parent[u][i];
                v=parent[v][i];
            }
        }
        u=parent[u][0];
    }
    return u;
}
ll path_nod(ll x){
    ll le=0,ri=path.size();
    while(le<ri){
        ll mid=(le+ri)/2;
        if(LCA(x,path[mid].n)==path[mid].n){
            ri=mid;
        }else{
            le=mid+1;
        }
    }
    return path[le].n;
}
struct ip{
    ll p,a,b;
};
ip inp[200010];
vector<double>er;
struct vy{
    ll v,y;
};
vy tree[2500000];
ll lazy[2500000];
void seg(ll n,ll s,ll e){
    tree[n]={0,0};
    lazy[n]=0;
    if(s==e)return;
    ll mid=(s+e)/2;
    seg(n*2,s,mid);
    seg(n*2+1,mid+1,e);
}
void propagate(ll n,ll s,ll e){
    if(lazy[n]!=0){
        if(s!=e){
            lazy[n*2]+=lazy[n];
            lazy[n*2+1]+=lazy[n];
        }
        tree[n].v+=lazy[n]*(e-s+1);
        tree[n].y+=lazy[n];
        lazy[n]=0;
    }
}
void upd(ll n,ll s,ll e,ll le, ll ri,ll v){
    propagate(n,s,e);
    if(ri<s||e<le)return;
    if(le<=s&&e<=ri){
        lazy[n]+=v;
        propagate(n,s,e);
        return;
    }
    ll mid=(s+e)/2;
    upd(n*2,s,mid,le,ri,v);
    upd(n*2+1,mid+1,e,le,ri,v);
    tree[n].v=tree[n*2].v+tree[n*2+1].v;
    tree[n].y=min(tree[n*2].y,tree[n*2+1].y);
}
ll Sum(ll n,ll s,ll e,ll le,ll ri){
    propagate(n,s,e);
    if(ri<s||e<le)return 1e18;
    if(le<=s&&e<=ri){
        return tree[n].y;
    }
    ll mid=(s+e)/2;
    return min(Sum(n*2,s,mid,le,ri),Sum(n*2+1,mid+1,e,le,ri));
}
ll Sumv(ll n,ll s,ll e,ll le,ll ri){
    propagate(n,s,e);
    if(ri<s||e<le)return 0;
    if(le<=s&&e<=ri){
        return tree[n].v;
    }
    ll mid=(s+e)/2;
    return Sumv(n*2,s,mid,le,ri)+Sumv(n*2+1,mid+1,e,le,ri);
}
ll N=600000;
vector<ll>er2;
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i=0;i<n-1;i++){
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    memset(parent,-1,sizeof(parent));
    lengths[1]=1;
    dfs(1,0);
    path.push_back({n,0});
    fd(1,0);
    ll len=1;
    for(int i=(ll)path.size()-1;i>=0;i--){
        wide[path[i].n]=len;
        len+=path[i].c;
    }
    for(int i=(ll)path.size()-1;i>=0;i--){
        er.push_back(wide[path[i].n]);
    }
    for(int j=0;j<MAX-1;j++){
        for(int i=2;i<=n;i++){
            if(parent[i][j]!=-1)parent[i][j+1]=parent[parent[i][j]][j];
        }
    }
    for(int i=1;i<=q;i++){
        cin >> inp[i].p;
        if(inp[i].p==1){
            cin >> inp[i].a >> inp[i].b;
        }else{
            cin >> inp[i].a;
        }
    }
    for(int i=1;i<=q;i++){
        ll T=path_nod(inp[i].a);
        ll D=lengths[inp[i].a]-lengths[T];
        if(inp[i].p==1){
            if(inp[i].b-D>=0){
                er.push_back(max(wide[1],wide[T]-(inp[i].b-D)));
                er.push_back(min(wide[n],wide[T]+(inp[i].b-D)));
            }
        }
    }
    sort(er.begin(),er.end());
    er.erase(unique(er.begin(),er.end()),er.end());
    //for(int i=0;i<er.size();i++)
    seg(1,1,N);
    for(int i=1;i<=q;i++){
        ll T=path_nod(inp[i].a);
        ll D=lengths[inp[i].a]-lengths[T];
        if(inp[i].p==1){
            ll T=path_nod(inp[i].a);
            ll D=lengths[inp[i].a]-lengths[T];
            if((inp[i].b-D)>=0){
                ll A=lower_bound(er.begin(),er.end(),wide[T]-(inp[i].b-D))-er.begin()+1;
                ll B=lower_bound(er.begin(),er.end(),wide[T]+(inp[i].b-D))-er.begin();
                upd(1,1,N,A,B,1);
            }
        }else{
            ll T=path_nod(inp[inp[i].a].a);
            ll D=lengths[inp[inp[i].a].a]-lengths[T];
            if((inp[inp[i].a].b-D)>=0){
                ll A=lower_bound(er.begin(),er.end(),wide[T]-(inp[inp[i].a].b-D))-er.begin()+1;
                ll B=lower_bound(er.begin(),er.end(),wide[T]+(inp[inp[i].a].b-D))-er.begin();
                upd(1,1,N,A,B,-1);
            }
        }
        ll LE=lower_bound(er.begin(),er.end(),wide[1])-er.begin()+1;
        ll RI=lower_bound(er.begin(),er.end(),wide[n])-er.begin();
        ll VA=Sum(1,1,N,LE,RI);

        if(VA>0){
            cout << "YES\n";
        }else{
            cout << "NO\n";
        }
    }

}