백준 25491 - Mexor tree (C++)

문제

• 문제 링크

  
   BOJ 25491 - Mexor tree 
  

• 문제 요약

$x$ $y$ $z$ : 정점 $x$와 $y$를 잇는 단순 경로 상의 정점들의 값들을 각각 $z$와 $XOR$ 연산을 시행한 값으로 바꾼다.

$b_i$ : 정점 $S$와 정점 $i$를 잇는 단순 경로 상의 정점들의 값들 중에 존재하지 않는 음이 아닌 정수 중 최솟값.



$N$개의 정점으로 이루어진 트리와, 각 정점의 정점값이 주어진다.
쿼리의 내용과 수열 $b_i$의 정의가 위와 같을 때, $Q$개의 쿼리를 모두 처리한 후 $b_1, b_2, ... b_N$ 을 출력하자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 300,000$

$0 ≤ a_i ≤ N$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리를 사용한 집합과 맵 (tree _ set / map)
• 그래프 이론 (graphs)
• 그래프 탐색 (graphs_traversal)
• 깊이 우선 탐색 (dfs)
• 트리 (trees)
• 최소 공통 조상 (lowest common ancestor)

풀이

주어진 쿼리를 크게 두가지 방식으로 처리할 수 있다.

트리 위 경로 쿼리답게 $Heavy-Light$ $Decomposition$의 강력함을 이용한다.

트리가 갖는 특성과, 동일한 값을 두 번 $xor$하면 제자리라는 $xor$의 특성을 이용한다.

처음 방식이야 구간 단위 업데이트 이므로 $Lazy$ $Propagation$을 적절히 이용하면 된다.

두번째 방식의 경우 약간의 관찰을 요구한다.
$x, y$에 대해 각각 루트로부터 이어지는 경로 위 모든 정점에 $z$를 $XOR$ 했다고 해보자.

그럼 루트로부터 $lca(x, y)$까지의 정점에는 변화가 없고, 나머지 $x ↔ y$ 의 경로 위 정점들엔 정상적으로 $z$가 $XOR$됨을 관찰할 수 있다.

물론 $lca(x, y)$도 $x ↔ y$ 의 경로에 포함되므로 추가적인 처리가 필요하다.

---

구체적으로 아래의 과정을 따라가자.

정점 $i$의 $XOR$ 업데이트 상태를 기록하는 배열 $rec[i]$를 정의하자.

$imos$법과 같은 테크닉에서, 업데이트 포인트를 찍어둔 후 최종 스위핑 한 번으로 결과를 도출할 수 있었다.

위에서의 관찰을 통해, 지금 언급한 테크닉을 트리에서 적용할 수 있게 된다.

업데이트 포인트는 $rec[x], rec[y]$가 되며 $a[lca(x, y)]$에 처리해주는 것도 잊지 말아야 한다.

선형 구조에선 단순히 반복문으로 스위핑을 진행했다면, 비선형 구조에선 $DFS$를 이용하면 된다.

모든 정점들마다 해당 정점의 서브트리의 $rec[]$ 을 받고, 처음 $a[]$와 $XOR$ 해주어 업데이트를 끝마치자.

---

이제 $S$를 시작으로 각 정점의 $MEX$값만 구하면 끝인데, 내가 사용한 방식의 설명은 아래의 링크로 대체한다.
왜 질문글을 쓰고 나서야 문제점이 보이는지 원..

삽질의 흔적과 독백

전체 코드

#include<bits/stdc++.h>
#define N 300001
using namespace std;
 
vector <int> Gr[N];
int rec[N], dep[N], dp[N][20];
int n, s, a[N], b[N];
 
void Input()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
 
    for (int i(1); i <= n; cin >> a[i++]);
    for (int u, v, i{}; ++i < n;)
    {
        cin >> u >> v;
        Gr[u].push_back(v);
        Gr[v].push_back(u);
    }
}
void LCAInit(int now, int depth)
{
    dep[now] = depth;
    for (int& next : Gr[now])
        if (!dep[next])
        {
            dp[next][0] = now;
            LCAInit(next, depth + 1);
        }
}
void TableDP()
{
    for (int j(1); j < 20; j++)
        for (int i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int getLCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    int diff(dep[u] - dep[v]);
 
    for (int i{}; diff; diff >>= 1, i++)
        if (diff & 1)
            u = dp[u][i];
    if (u ^ v)
    {
        for (int i(19); !!~i; i--)
            if (dp[u][i] ^ dp[v][i])
                u = dp[u][i], v = dp[v][i];
        u = dp[u][0];
    }
    return u;
}
void Query()
{
    int q; cin >> q;
    while (q--)
    {
        int x, y, z; cin >> x >> y >> z;
        int lca(getLCA(x, y));
 
        rec[x] ^= z, rec[y] ^= z, a[lca] ^= z;
    }
}
void Calxor(int now, int prev)
{
    for (int& next : Gr[now])
        if (next ^ prev)
        {
            Calxor(next, now);
            rec[now] ^= rec[next];
        }
    a[now] ^= rec[now];
}
 
set <int> mex;
int cnt[N << 1];
void Getmex(int now, int prev)
{
    mex.erase(a[now]);
    cnt[a[now]]++;
 
    b[now] = *mex.begin();
    for (int& next : Gr[now])
        if (next ^ prev)
            Getmex(next, now);
 
    if (!--cnt[a[now]]) mex.insert(a[now]);
}
int main()
{
    Input();
    LCAInit(s, 1);
    TableDP();
    Query();
    Calxor(s, s);
 
    for (int i{}; i <= N; mex.insert(i++));
    Getmex(s, s);
    for (int i(1); i <= n; cout << b[i++] << ' ');
}

comment

끝