티스토리 뷰

반응형

문제 링크


2018/07/26 추가내용.

참고) post-order대신 pre-order로 순회 해도 같은 효과를 볼 수 있으며, 코드를 조금 더 편하게, 더 직관적으로 짤 수 있다.

pre-order로 순회하는 코드는 여기를 참고하자.



1번 정점을 루트로 하는 트리가 주어지고, M개의 질의가 주어졌을 때 다음과 같은 명령을 실행한다.

  • 1 x꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.
  • 2 x y꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y를 XOR함 .


얼핏 봐선 그냥 하면 되는거 아닌가 싶겠지만 범위가 굉장히 크다.

정점의 수 N과 질의의 수 M에 대해

$(1\leq N \leq 100,000)$, $(1\leq M \leq 500,000)$ 

의 범위를 가진다.


질의가 주어질 때마다 정직하게 연산을 하게되면

이런 트리에서 쿼리 명령으로

"1 1"이나

"2 1 10"이 주어질 경우 한 번의 질의에 $O(N)$만큼 시간이 걸린다. M개의 쿼리가 모두 저런 식으로 주어졌을 때 $O(NM)$의 시간복잡도로 당연히 시간 초과를 받게 된다.


따라서 우리는 다른 방법을 찾아야 한다.

결론부터 말하면 세그먼트 트리를 이용하여 풀 수 있다. 세그먼트 트리를 모른다면 다음 링크에서 공부하고 오자.

백준 - 세그먼트 트리

백준 - 세그먼트 트리 lazy propagation


주어진 트리에서 어떤 부모와 그 모든 자손을 하나의 구간으로 볼 수 있기 때문에 세그먼트 트리로 해결할 수 있다. 하지만 이를 구현하기가 까다롭다.

트리의 모든 정점을 세그먼트 트리의 리프 노드로 만들되, 구간 업데이트를 적용하기 위해 자손과 부모를 연속하게 배치해야 한다. 또한 어떤 정점이 주어졌을 때 그 정점과 모든 자손이 세그먼트 트리의 어느 범위에 속하는지 알 수 있어야 한다.



문제의 예제 2번을 예로 들어 트리를 어떻게 세그먼트 트리로 만들 것인지 단계별로 살펴보자.

먼저 어떤 정점 $x$에 대해, $x$가 세그먼트 트리에서 몇 번째 리프노드인지 저장하는 $numbering$, $x$의 자식의 수가 몇 개인지 저장하는 $numChild$배열이 필요하다. 이 배열들의 쓰임새는 나중에 설명하겠다.


일단 정점을 재배치하기 위해 트리를 후위순회로 탐색한다. 이는 항상 자식이 부모보다 먼저 나열됨을 보장하기도 하면서, 자식의 수를 쉽게 구할 수 있는 방법이다.


$step\,0)$

초기상태이다. 


 정점 번호

1

2

3

4

5

6

7

numbering

 

 

 

 

 

 

 

numChild

 

 

 

 

 

 

 






$step\,1)$

처음으로 방문하는 정점은 2번 정점이고 자식은 없다.


 정점 번호

1

2

3

4

5

6

7

numbering


1






numChild


0











$step\,2)$

두 번째로 3번 정점을 방문한다. 자식은 없다.


 정점 번호

1

2

3

4

5

6

7

numbering


1

2





numChild


0

0










$step\,3)$

세 번째로 5번 정점을 방문한다. 


 정점 번호

1

2

3

4

5

6

7

numbering


1

2


3



numChild


0

0


0








$step\,4)$

네 번째로 7번 정점을 방문한다.


 정점 번호

1

2

3

4

5

6

7

numbering


1

2


3


4

numChild


0

0


0


0






$step\,5)$

다섯 번째로 6번 정점을 방문하게 된다. 자식의 수는 1이다.


 정점 번호

1

2

3

4

5

6

7

numbering


1

2


3

5

4

numChild


0

0


0

1

0






$step\,6)$

여섯 번째로 4번 정점을 방문하게 된다. 자식의 수는 3이다.


 정점 번호

1

2

3

4

5

6

7

numbering


1

2

6

3

5

4

numChild


0

0

3

0

1

0






$step\,7)$

마지막으로 1번 정점을 방문하게 된다. 자식의 수는 6이다.


 정점 번호

1

2

3

4

5

6

7

numbering

7

1

2

6

3

5

4

numChild

6

0

0

3

0

1

0






트리를 세그먼트 트리로 변환하기 위한 사전 준비가 끝났다. 위 과정은 코드상에서 init_seg_data(int)함수에 구현되어있다.




우선 $numbering$배열을 이용해 정점들의 순서를 재배열한 뒤(사실 코드상에선 그냥 위의 과정 중에 배열 p에다가 순서대로 저장한다) 세그먼트 트리를 만든다. 이 세그먼트 트리는 가중치를 저장하지만 아래 그림에선 나타내지 않도록 하겠다.

세그먼트 트리의 $i$번째 리프노드가 원래 트리의 $n$번 정점이라면, 이를 다음과 같이 나타내자.



세그먼트 트리를 만들어서 그려보면

이런 모습이다.


세그먼트 트리를 만들었으니 이제 쿼리를 해결하자. 어떤 정점 $x$가 주어지면 세그먼트 트리에서 그 정점의 위치 $i$는 $numbering[x]$임을 알고있다. 후위순회의 결과를 기반으로 정점들이 재배열되었기 때문에, 자신보다 자식이 항상 앞에 있으면서 연속적으로 배치되어 있다. 따라서 $x$의 모든 자손과 자기 자신을 포함하는 범위는 $[i - numChild[x], i]$이다. 이해가 안간다면 위 그림과 원래 트리의 그림을 비교해보자. 쉽게 알 수 있다.


쿼리문을 수행해야 하는 세그먼트 트리의 범위를 구했으므로 문제를 쉽게 풀 수 있게 된다.

주의할 점은 lazy update에서 변형이 조금 일어나는데, 어떤 수 $x$에 대해 $x\oplus x = 0$이므로 XOR연산을 $k$번 해야할 때 $k$가 짝수이면 연산하지 않아도 되고, $k$가 홀수이면 한 번만 XOR해주면 된다.


정답 코드


반응형
댓글
  • 프로필사진 알고싶다 따라서 x의 모든 자손과 자기 자신을 포함하는 범위는 [i−numChild[x],i]이다. 이해가 안간다면 위 그림과 원래 트리의 그림을 비교해보자. 쉽게 알 수 있다
    에서 i는 어디서 나오는 건가요?
    트리재구성이 어려운데요.
    2019.03.09 22:41
  • 프로필사진 degurii i == numbering[x] 입니다.
    초창기에 풀었던 방식이라 포스트 오더의 순서를 기반으로 정점들을 재배치하기때문에 덜 직관적입니다. 글 상단에 프리오더로 순회해서 정점들을 배치하는 코드가 있습니다. 그게 좀 더 이해하기 쉬우실거에요
    2019.03.10 15:46 신고
  • 프로필사진 구데타마 와! Calculate! 2
    2019.08.07 11:31 신고
  • 프로필사진 degurii 와! 계산!! 2019.08.07 15:03 신고
댓글쓰기 폼