티스토리 뷰

알고리즘 관련/BOJ

BOJ)13309 트리

JASON 자손9319 2017. 6. 21. 17:06

문제:icpc.me/13309


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


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


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


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


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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 * + 1= max(lazy[node * + 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&&<= 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 * + 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&&<= hi)return seg[node];
    int mid = (x + y) >> 1;
    return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * + 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, 11, n);
    int ly = dph[y] - query(y, y, 11, n);
    for (int i = 20; i >= 0; i--) {
        if (par[x][i] && lx >= (<< i)) {
            lx -= (<< i);
            x = par[x][i];
        }
    }
    for (int i = 20; i >= 0; i--) {
        if (par[y][i] && ly >= (<< i)) {
            ly -= (<< 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]], 11, n);
            else
                update(idx[y], leaf[idx[y]], dph[idx[y]], 11, n);
        }
        else 
            printf("%s\n", chk(idx[x], idx[y]) ? "YES" : "NO");
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1444 숌 언어  (0) 2017.07.05
BOJ)9023 연습시즌  (0) 2017.06.22
BOJ)13309 트리  (1) 2017.06.21
BOJ)2507 공주 구하기  (0) 2017.06.18
BOJ)12869 뮤탈리스크  (0) 2017.06.18
BOJ)12922 블럭 퍼즐  (0) 2017.06.15
댓글
댓글쓰기 폼