BOJ)13309 트리

문제:icpc.me/13309

트리에서 두 가지 쿼리를 처리하는 문제이다.

첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 

두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다.

오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다.

우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다.

이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다.

그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수 있는 만큼 올라 간 뒤 두 정점이 같은지 비교하는것으로 확인을 한다고 가정한다면

정점 A와 정점 A의 부모를 단절시키는 케이스는 정점A가 커버하는 구간이 올라갈 수 있는 최대 깊이를 정점 A의 깊이로 설정해 줌으로서 해결할 수 있다.

구간에 대한 최댓값 연산은 lazy propagation을 이용한 세그먼트 트리로 가능하고 부모를 따라 올라가는건 lca의 방법으로 해결해 줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
vector<vector<int>> vt;
int n, q, idx[200020], leaf[200020], par[200020][22], p[200020], dph[200020], id, seg[800020], lazy[800020];
void u_lazy(int node, int x, int y) {
    if (!lazy[node])return;
    seg[node] = max(seg[node], lazy[node]);
    if (x != y) {
        lazy[node * 2] = max(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
    }
    lazy[node] = 0;
}
int update(int lo, int hi, int val, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return seg[node];
    if (lo <= x&&y <= hi) {
        lazy[node] = max(lazy[node], val);
        u_lazy(node, x, y);
        return seg[node];
    }
    int mid = (x + y) >> 1;
    return seg[node] = max(update(lo, hi, val, node * 2, x, mid), update(lo, hi, val, node * 2 + 1, mid + 1, y));
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)return -INF;
    if (lo <= x&&y <= hi)return seg[node];
    int mid = (x + y) >> 1;
    return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
void getid(int here) {
    idx[here] = ++id;
    for (auto next : vt[here])
        getid(next);
}
int dfs(int here) {
    int ret = idx[here];
    for (auto next : vt[here]) {
        par[idx[next]][0] = idx[here];
        dph[idx[next]] = dph[idx[here]] + 1;
        ret = max(ret, dfs(next));
    }
    return leaf[idx[here]] = ret;
}
bool chk(int x, int y) {
    int lx = dph[x] - query(x, x, 1, 1, n);
    int ly = dph[y] - query(y, y, 1, 1, n);
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] && lx >= (1 << i)) {
            lx -= (1 << i);
            x = par[x][i];
        }
    }
    for (int i = 20; i >= 0; i--) {
        if (par[y][i] && ly >= (1 << i)) {
            ly -= (1 << i);
            y = par[y][i];
        }
    }
    return x == y;
}
int main() {
    scanf("%d%d", &n, &q);
    vt.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &p[i]);
        vt[p[i]].push_back(i);
    }
    getid(1);
    dfs(1);
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= n; j++)
            par[j][i] = par[par[j][i - 1]][i - 1];
    }
    for (int i = 0; i < q; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if (z) {
            int f = chk(idx[x], idx[y]);
            printf("%s\n", f ? "YES" : "NO");
            if (f)
                update(idx[x], leaf[idx[x]], dph[idx[x]], 1, 1, n);
            else
                update(idx[y], leaf[idx[y]], dph[idx[y]], 1, 1, n);
        }
        else 
            printf("%s\n", chk(idx[x], idx[y]) ? "YES" : "NO");
    }
    return 0;
}