1. 풀이
먼저 쿼리를 처리하는 방법을 생각해보자. 만약 온라인이였다면 HLD를 만들고 lazy xor seg를 통해 \(O(log^2N)\)에 쉽게 처리할 수 있다. 이 문제에서는 쿼리가 한번에 들어오므로 다른 효율적인 방법을 생각해보자.
\(u, v\)에 대한 단순 경로는, \(t = LCA(u, v)\)라고 정의할 때, \(u - t - v\)의 직선 경로 \(2\)개로 생각할 수 있다. 그러므로 트리에서 구간합을 생성하는 것과 비슷하게 해주면 빠르게 처리할 수 있다.
직선 경로 \(a - b\)에 모두 xor을 하려면, \(a\)에 xor한 후 \(b\)에 도달할 때까지 전이를 해주고, \(b\) 이후에는 다시 똑같은 수를 xor하여 이후 노드에는 영향을 주지 않게 해주면 된다. 즉 특정 구간에 +\(1, -1\)한후 구간합을 만드는 것과 똑같이 할 수 있다는 것이다.
조금 구현이 까다로우므로 자식에서 부모로 올라가면서 처리해주었다. 자식에서 부모로 올라가는 경우는 \(1\)개이므로 이 점을 활용하면 쉽게 구현할 수 있다. 또한 \(t == a, t == b\) 이런 경우도 case work하여 잘 처리해야 된다.
모든 쿼리를 처리한 후 \(MEX\)를 구하는 방법을 생각해보자. 정점 \(S\)에서 정점 \(i\)의 단순 경로 중 \(MEX\)를 구하는 것이다. \(S\)를 루트로 하여 새롭게 트리를 생각하면 모두 직선 경로이므로 쉽게 생각할 수 있다.
\(MEX\)를 빠르게 구하는 방법을 먼저 생각해보자. \(MEX\)의 결과값은 \(2^{20}\) 이하이므로, \(2^{20}\) 크기고, 자식들의 초기값이 모두 \(1\)인 Seg를 만들자.
백준 2243 사탕 상자 처럼 특정한 수가 들어왔다면 Seg에서 그 값의 값을 \(0\)으로 만들어준다. 그리고 \(MEX\)는 Seg안에 있는 값들 중 \(1\)번째 값이 된다.
그러므로 정점 \(S\)에서 시작하여 dfs를 하면 모든 정점에 대한 \(MEX\)를 빠르게 찾아줄 수 있다.
2. 소스코드
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
|
#include <bits/stdc++.h>
using namespace std;
struct MEXSeg {
int n;
vector<int> seg;
void init(int _n) {
n = _n;
seg.resize(4*n);
init(1, 0, n - 1);
}
int init(int num, int s, int e) {
if (s == e) return seg[num] = 1;
int mid = s + e >> 1;
return seg[num] = init(2 * num, s, mid) + init(2 * num + 1, mid + 1, e);
}
int update(int num, int s, int e, int idx, int p) {
if (idx < s || e < idx) return seg[num];
if (s == e) return seg[num] += p;
int mid = s + e >> 1;
return seg[num] = update(2*num, s, mid, idx, p) + update(2*num+1, mid+1, e, idx, p);
}
void update(int idx, int p) { update(1, 0, n-1, idx, p); }
int query(int num, int s, int e, int k) {
if (s == e) return s;
int mid = s + e >> 1;
if (k <= seg[2 * num])
return query(2 * num, s, mid, k);
else
return query(2*num+1, mid+1, e, k-seg[2*num]);
}
int query() { return query(1, 0, n-1, 1); }
}mex;
const int LV = 20;
const int MAX = 300001;
vector<int> V[MAX];
int dp[LV + 1][MAX], dep[MAX], ind[MAX];
void dfs(int pos, int d=1, int p = 0) {
dp[0][pos] = p;
dep[pos] = d;
for (int i = 1; i < LV; i++)
dp[i][pos] = dp[i - 1][dp[i - 1][pos]];
for (int w : V[pos]) {
if (w == p) continue;
ind[pos]++;
dfs(w, d+1, pos);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int diff = dep[a] - dep[b];
for (int i = 0; diff; i++) {
if (diff & 1) a = dp[i][a];
diff >>= 1;
}
if (a == b) return a;
for (int i = LV - 1; i >= 0; i--)
if (dp[i][a] != dp[i][b]) a = dp[i][a], b = dp[i][b];
return dp[0][a];
}
int arr[MAX], xo[MAX], out[MAX], cnt[1 << 21], ans[MAX];
void solve(int pos, int p = 0) {
if (--cnt[arr[pos]] == 0) mex.update(arr[pos], -1);
ans[pos] = mex.query();
for (int w : V[pos]) {
if (w == p) continue;
solve(w, pos);
}
if (++cnt[arr[pos]] == 1) mex.update(arr[pos], 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, s; cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
}
dfs(1);
int k; cin >> k;
while (k--) {
int a, b, c; cin >> a >> b >> c;
int t = lca(a, b);
if (a == b)arr[a] ^= c;
else if (t == a)
out[t] ^= c, xo[b] ^= c;
else if (t == b)
out[t] ^= c, xo[a] ^= c;
else {
xo[a] ^= c, xo[b] ^= c;
arr[t] ^= c;
}
}
queue<int> q;
for (int i = 1; i <= n; i++)
if (!ind[i]) q.push(i);
while (q.size()) {
int top = q.front(); q.pop();
xo[dp[0][top]] ^= xo[top] ^ out[top];
if (--ind[dp[0][top]] == 0) q.push(dp[0][top]);
}
for (int i = 1; i <= n; i++) {
arr[i] ^= xo[i];
}
fill(cnt, cnt + (1 << 21), 1);
mex.init(1 << 21);
solve(s);
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
return 0;
}
|
cs |
'PS > 백준' 카테고리의 다른 글
[백준 26113] Two Choreographies (0) | 2022.11.22 |
---|---|
[백준 5979] 납땜하기 (2) | 2022.09.22 |
[백준 25500] 무자비한 최단 경로 (0) | 2022.09.14 |
[백준 15506] 정원사 (0) | 2021.12.21 |
[백준 20052] 괄호 문자열 ? (0) | 2021.12.21 |