[Algorithm] C++ 백준 15782번: Calculate! 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

예제 입력 1:
5 4
1 2
2 3
2 4
3 5
1 2 3 4 5
1 1
2 3 100
2 1 94
1 4

예제 출력 1:
1
90

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void dfs(int u, int parent) {
    in_time[u] = ++timer;
    euler_tour[timer] = u;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    out_time[u] = timer;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void push(int node, int start, int end) {
    if (lazy[node] != 0) {
        // XOR 적용: 홀수 개 원소만 영향
        if ((end - start + 1) % 2 == 1) {
            tree[node] ^= lazy[node];
        }
        if (start != end) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        lazy[node] = 0;
    }
}

  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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

// 더 많은 정보는 42jerrykim.github.io 에서 확인할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
vector<int> adj[MAXN];
int weight[MAXN];
int in_time[MAXN], out_time[MAXN];
int euler_tour[MAXN * 2];
int timer = 0;

struct SegmentTree {
    int tree[MAXN * 8];
    int lazy[MAXN * 8];
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            // XOR의 특성: 홀수 개의 원소에만 영향
            if ((end - start + 1) % 2 == 1) {
                tree[node] ^= lazy[node];
            }
            if (start != end) {
                lazy[node * 2] ^= lazy[node];
                lazy[node * 2 + 1] ^= lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = weight[euler_tour[start]];
        } else {
            int mid = (start + end) / 2;
            build(node * 2, start, mid);
            build(node * 2 + 1, mid + 1, end);
            tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
        }
    }
    
    void update(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] ^= val;
            push(node, start, end);
            return;
        }
        
        int mid = (start + end) / 2;
        update(node * 2, start, mid, l, r, val);
        update(node * 2 + 1, mid + 1, end, l, r, val);
        
        push(node * 2, start, mid);
        push(node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
    }
    
    int query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        
        push(node, start, end);
        
        if (start >= l && end <= r) {
            return tree[node];
        }
        
        int mid = (start + end) / 2;
        int left_result = query(node * 2, start, mid, l, r);
        int right_result = query(node * 2 + 1, mid + 1, end, l, r);
        return left_result ^ right_result;
    }
} seg;

void dfs(int u, int parent) {
    in_time[u] = ++timer;
    euler_tour[timer] = u;
    
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    
    out_time[u] = timer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }
    
    dfs(1, 0);
    
    seg.build(1, 1, n);
    
    for (int i = 0; i < m; i++) {
        int type;
        cin >> type;
        
        if (type == 1) {
            int x;
            cin >> x;
            cout << seg.query(1, 1, n, in_time[x], out_time[x]) << '\n';
        } else {
            int x, y;
            cin >> x >> y;
            seg.update(1, 1, n, in_time[x], out_time[x], y);
        }
    }
    
    return 0;
}