[백준 13309] 트리

문제

www.acmicpc.net/problem/13309

 

알고리즘

HLD

 

풀이

트리에서 두 노드를 잇는 경로가 존재하는지 묻는 문제입니다. 추가적으로 조건에 따라 간선을 끊어주기도 합니다.

 

트리에서 부모 노드는 유일합니다. 즉 부모 노드로 가는 간선은 유일하므로 모든 간선은 루트를 제외한 모든 노드들로 표현이 가능합니다. HLD를 통해 트리를 일자 형태인 배열로 나타낸 후, 세그먼트 트리를 이용해 구간의 최솟값을 구하면 경로가 존재함을 알 수 있습니다. 최솟값이 1이라면 경로가 존재, 0이라면 끊어져 있는 것입니다. 간선을 끊을 때, 세그먼트 트리에 0 값을 업데이트하면 됩니다. 세그먼트 트리에 접근할 때는 $idx$배열을 통해 접근해야 함을 유의하도록 합시다

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
#define FAST                                                                                                           \
    cin.tie(NULL);                                                                                                     \
    cout.tie(NULL);                                                                                                    \
    ios::sync_with_stdio(false)
using namespace std;

const int MAXN = 200001;

int N, M, Q, cnt, len;
vector<int> adj[MAXN];

int top[MAXN], pa[MAXN], sz[MAXN], idx[MAXN], bot[MAXN];
vector<int> tree;

int dfs(int here) {
    sz[here] = 1;
    for (auto& there : adj[here]) {
        if (pa[here] ^ there) {
            pa[there] = here;
            sz[here] += dfs(there);
            int& h = adj[here][0];

            if (h == pa[here] || sz[h] < sz[there])
                swap(h, there);
        }
    }
    return sz[here];
}

void hld(int here) {
    idx[here] = cnt++;
    for (auto there : adj[here]) {
        if (there ^ pa[here]) {
            top[there] = there == adj[here][0] ? top[here] : there;
            hld(there);
        }
    }
}

void update(int i, int v) {
    tree[i += len] = v;
    i >>= 1;
    for (; i > 0; i >>= 1) {
        tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
    }
}

int query(int l, int r) {
    l += len;
    r += len;
    int ret = 1;
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1)
            ret = min(ret, tree[l++]);
        if (!(r & 1))
            ret = min(ret, tree[r--]);
    }
    return ret;
}

int solve(int u, int v) {
    int ret = 1;
    while (top[u] ^ top[v]) {
        if (sz[top[u]] < sz[top[v]])
            swap(u, v);

        ret = min(ret, query(idx[top[v]], idx[v]));
        v = pa[top[v]];
    }
    if (idx[u] > idx[v])
        swap(u, v);
    ret = min(ret, query(idx[u] + 1, idx[v]));
    return ret;
}

int main() {
    FAST;
    cin >> N >> Q;
    len = pow(2, ceil(log2(N)));
    tree.resize(len << 1, 1);
    for (int i = 1; i < N; ++i) {
        int u;
        cin >> u;
        --u;
        adj[u].emplace_back(i);
        adj[i].emplace_back(u);
    }
    dfs(0);
    hld(0);

    while (Q--) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        int val = solve(a, b);

        if (val)
            cout << "YES\n";
        else
            cout << "NO\n";

        if (c == 1) {
            if (val) {
                update(idx[a], 0);
            } else {
                update(idx[b], 0);
            }
        }
    }
    return 0;
}