tree

Euler Tour Technique

트리의 서브트리 쿼리에 유용하다.

문서참조(/all/algorithm/doc/tree/Euler Tour Technique.html)

Heavy Light Decomposition

트리의 경로 쿼리에 유용하다.

문서참조(/all/algorithm/doc/tree/Heavy Light Decomposition.html)

Centroid Decomposition

트리에서 분할정복에 유용하다. x를 지나는 모든 경로에 대한 계산값을, 센트로이드 트리에서 정점 x의 값과 그 센트로이드 트리에서의 x의 조상들의 값을 사용해서 계산할 수 있다. 그리고 조상노드가 logN개이므로 복잡도가 개선된다는듯. NOTE: x의 조상들에 대한 계산을 할때는 원본트리의 값(거리 등)을 사용해서 계산해줘야함. x의 센트로이드 부모가 원본 트리에서는 인접하지 않을 수 있기 때문임.

https://ps.mjstudio.net/centroid-decomposition

https://codeforces.com/blog/entry/73707

https://medium.com/carpanese/an-illustrated-introduction-to-centroid-decomposition-8c1989d53308

https://github.com/infossm/infossm.github.io/blob/master/_posts/2021-04-14-centroid-of-a-tree.md

https://arnold518.tistory.com/67

https://lego0901.tistory.com/12

https://seastar105.tistory.com/42

트리의 경로 DP

초록책 p163의 테크닉을 알면 굉장히 유용한듯. (계산할때 자기 자신이 온 경로를 제외하기 위해 최적후보 값을 2개 가지고 있는 방법.)

센트로이드?

빌라봉

Small to Large on Tree

모든 서브트리에 대해, 후손노드들 값으로 구성되는 어떤 자료구조가 필요한 경우, dfs하면서 해당 자료구조를 스위핑하며 관리해줄 수 있다. 자료구조에 원소를 추가하는게 O(Q)라고 할 때, Small To Large를 적용하면 전체 복잡도가 amortized O(N*Q*logN)가 된다. 참고로 후손노드들 값으로 구성된 자료구조대신, 후손노드들 값으로 구성된 세그먼트 트리에 대한 쿼리로 대체 가능한 경우, Euler Tour를 사용해서 해당 서브트리 구간에 쿼리를 날려도 된다.

BOJ숲게임 등 많음

Tree Rerooting

루트없는 트리에서 각 트리정점이 루트라고 가정할때의 값 구하는 방법. 모든 노드에 대해 각 노드가 루트인 경우의 값을 모두 구하는게 한 노드에 대해 구하는 시간복잡도와 동일할 수 있다. 핵심은, 임의의 한 노드에 대해 DP를 하고 그 결과를 이용해 parent subtree value를 관리해주면서 dfs하는 것.

일단 한 정점에 대해서 유형1을 수행하자. 이제 각 정점x마다 서브트리값val(x)를 가지고 있을것이다. 들어가는 자식을 ch[x]라고 할때, 자식ch[x]가 루트라고 가정하면 그 직계자손들의 값은 동일한게 자명하고, 남은 ch[x]의 부모를 포함하는 하나의 서브트리값은, x의 부모 p[x]가 포함된 서브트리값에 x의 형제들(즉, p[x]의 직계자손들중 x가 아닌 것)값을 추가하여 구할 수 있다. 형제들 값을 합칠때 naive하게 짜면 N^2이 될 수 있는데, 역연산이 가능하면 간단하고, 역연산 불가능하더라도 prefix누적배열과 suffix누적배열을 전처리해두면 (amortized) N정도에 합칠 수 있다.

그리고 복잡도에 대해서 한가지 재밌는점은 각 정점x가 그 자식개수만큼 루프를 돌아도 전체 시간복잡도는 O(N)이다. 얼핏 코드만 봐서는 복잡도 보장이 잘 안되는것 같지만 꼭 이해하고 기억해두는것을 추천한다. 그래프에서 각 정점을 한번만 방문하면서 그 인접한 정점들의 목록의 루프를 돌면 루프는 항상 2*E번 실행되는데, 왜냐하면 각 간선별로 연결된 정점은 2개이므로 그 양쪽 정점에서 한번씩 총 두번 세지기 때문. 이것을 트리에도 그대로 적용하면 2*N번 루프를 도는것이다.

https://www.acmicpc.net/problem/7812

https://codeforces.com/contest/1498/submission/111416759

https://www.acmicpc.net/problem/15647

1289번, (ab+ac+ad+bc+bd+cd) = ((a+b+c+d)^2-(a^2+b^2+c^2+d^2))/2

https://codeforces.com/blog/entry/20935

Convolution on Tree

노드x의 자식들에 대한 dp값의 naive convolution은 길이를 매번 필요한만큼 딱 맞춰서 사용했을때 전체수행시간은 O(N^2)이다. O(N^3)이 아니라는게 놀라운 사실. KOI검은돌 등.

infimal convolution을 포함해서, 다음과 같은 과정이 주로 사용된다. 처음은 정점 x하나만 있는 트리와 x의 첫번째 자식의 convolution을 구한다. 다음에는 방금 합친 트리와 x의 두번째 자식의 convolution을 구한다. 이걸 모든 자식을 합칠때까지 반복한다. 코드상으로는 dp[x][~]가 사용되서 이해못했었는데, k번째 자식을 합칠타이밍에 dp[x][~]값에는 보통 k-1번째 자식까지 합친 값을 저장하고 있다. 당연히 k번째 자식의 서브트리값은 dp[g[x][k]][~]에 존재하니 두 값을 convolute하면 끝.

트리에서 distinct 조건N

서브트리 x에서 k개 뭔가 선택하는 문제가 있다고 하자. 그게 x에 영향을 주려면 최소한 두개의 자식서브트리에 나누어져야 x를 지나다니는데, distinct조건을 강제하는게 생각보다 어렵다. k개를 나누어 처리해보면 convolution내지는 infimal convolution꼴이 나오는데, 이렇게 그냥 조건없이 푼 정보를 가지고 distinct조건을 지키도록 dp2를 구해줄 수 있다. 자세한건 17674번 제출을 살펴보자. dp정의가 약간 꼬여있어서 dp[0]가 아니라 dp[tsz]가 하나도 선택안한(?)것인걸 생각하며 코드를 봐야하지만 아무튼 좋은 예제이다.

TODO

마리오와 사악한 키노피오 && Cyclic Distance

19530 숭고한 마라톤 대회

17624 검은돌

17674 특별관광도시

BOJ 20198 Papričice