백준 30092 - 슥삭슥삭 나무자르기 (C++)

문제

• 문제 링크

  
   BOJ 30092 - 슥삭슥삭 나무자르기 
  

• 문제 요약

$N$개의 정점으로 이루어진 트리가 주어진다.
아래 쿼리를 수행하는 프로그램을 작성하자.



$a$ $b$ $c$ $d$ : 정점 $a$에서 $b$로 가는 최단 경로에 속한 모든 간선을 제거했을 때, 정점 $c$에서 $d$로 가는 경로가 존재하면 $YES$, 존재하지 않으면 $NO$를 출력한다.

• 제한

TL : $4$ sec, ML : $1024$ MB




$2 ≤ N ≤ 100,000$

$1 ≤ Q ≤ 300,000$

각 쿼리는 독립적이다.

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• heavy-light 분할 (heavy-light decomposition)
• 세그먼트 트리 (segment tree)
• 느리게 갱신되는 세그먼트 트리 (lazy propagation)

풀이

아마 출제자가 의도한 정해는 $LCA$ + $Case$_$Work$ 였을 것 같다.

나도 처음에 케웍을 좀 끄적이다가 그냥 $hld$를 박았는데, 케웍 난이도는 대충 이 문제 랑 비슷하지 않을까싶다.

여튼 문제로 돌아와서,
간선이 끊어진 상태에 $1$의 가중치, 끊어지지 않은 상태에 $0$의 가중치를 부여한다고 생각해보자.

그럼 매 쿼리마다 다음의 시뮬레이션을 돌려줄 수 있다. 시간 복잡도는 쿼리 당 상수가 좀 붙은 $O(log^2N)$.

$a-b$의 경로 상에 $1$의 가중치를 부여한다.

$c-d$의 경로 상에 합쿼리를 날려 결과가 $0$이라면 $YES$, 양수라면 $NO$를 출력한다.

$a-b$의 경로 상에 부여한 $1$의 가중치를 제거한다.

전체 코드

#include<bits/stdc++.h>
#define N 100001
using namespace std;
 
vector <int> edge[N], tree[N];
int top[N], in[N], par[N], dep[N], sz[N];
int seg[1 << 18], lz[1 << 18];
int n, q;
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int u, v, i{}; ++i < n;)
    {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
}
void hldInit(int now)
{
    sz[now] = 1;
    for (int& next : edge[now])
        if (!sz[next])
        {
            dep[next] = dep[now] + 1;
            par[next] = now;
            hldInit(next);
            sz[now] += sz[next];
            tree[now].push_back(next);
 
            if (sz[tree[now][0]] < sz[next]) swap(tree[now][0], tree[now].back());
        }
}
int cur{};
void hldETT(int now)
{
    in[now] = ++cur;
    for (int& next : tree[now])
    {
        top[next] = next ^ tree[now][0] ? next : top[now];
        hldETT(next);
    }
}
void propagation(int n, int s, int e)
{
    if (lz[n])
    {
        seg[n] += lz[n];
        if (s ^ e)
        {
            lz[n << 1] += lz[n];
            lz[n << 1 | 1] += lz[n];
        }
        lz[n] = 0;
    }
}
int segUpdate(int n, int s, int e, int l, int r, int val)
{
    propagation(n, s, e);
    if (s > r || e < l) return seg[n];
    if (s >= l && e <= r)
    {
        lz[n] += val;
        propagation(n, s, e);
        return seg[n];
    }
    int m(s + e >> 1);
    return seg[n] = segUpdate(n << 1, s, m, l, r, val) + segUpdate(n << 1 | 1, m + 1, e, l, r, val);
}
int segQuery(int n, int s, int e, int l, int r)
{
    propagation(n, s, e);
    if (s > r || e < l) return 0;
    if (s >= l && e <= r) return seg[n];
    int m(s + e >> 1);
    return segQuery(n << 1, s, m, l, r) + segQuery(n << 1 | 1, m + 1, e, l, r);
}
void hldUpdate(int x, int y, int val)
{
    while (top[x] ^ top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        segUpdate(1, 1, n, in[top[x]], in[x], val);
        x = par[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    segUpdate(1, 1, n, in[x] + 1, in[y], val);
}
int hldQuery(int x, int y)
{
    while (top[x] ^ top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        if (segQuery(1, 1, n, in[top[x]], in[x])) return 1;
        x = par[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return segQuery(1, 1, n, in[x] + 1, in[y]);
}
void Query()
{
    while (q--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        hldUpdate(a, b, 1);
        cout << (hldQuery(c, d) ? "NO" : "YES") << '\n';
        hldUpdate(a, b, -1);
    }
}
int main()
{
    Input();
    hldInit(1);
    hldETT(1);
    Query();
}

comment

끝