#16748 Colorful Tree

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

 

집에 오는 길에 문제를 읽고 풀었는데, 난이도가 좀 높게 잡혀 있길래 나의 풀이가 정말 맞는지 끝없이 의심하며 왔다.

 

아무튼, 각 색에 대해서 트리의 크기를 구하는 것이다.

당연히 할 수 있는 생각이 모든 색에 대해 트리의 크기를 미리 계산해 두고, 꾸준히 업데이트 하는 것이다.

한 번에 한 색만 정보가 바뀌기 때문에 대충 가능할 것이라는 생각이 든다.

 

X가 색이 Y가 된다고 가정하자.

그러면 그냥 나머지 Y의 색을 가진 점들 기준으로는 X를 추가하는 것과 다를게 없다.

따라서 X를 추가한다고 생각하자.

X에 대해서 바로 왼쪽에 있는 걸 L, 바로 오른쪽에 있는 것을 R이라고 하자.

엄밀히 이야기하면 색이 Y인 점들 중 dfs를 하였을 때 X보다 직전/직후에 방문하는 점들이다.

그러면 X가 추가되는 것은 LCA(X, L)과 X가 이어지거나, LCA(X, R)이 X과 이어지는 것임을 알 수 있다.

따라서 둘 중에서 더 작은 값을 answer[Y]에 더해주면 된다.

 

근데 L, R이 존재하지 않을 수 있다.

L, R이 둘 다 없으면, 아무것도 없던 것에서 X만 뿅 생긴 것이니 answer[Y]가 -1에서 0이 되는 것이다.

일반성을 잃지 않고 R만 없다고 가정하자.

그러면 Y 중에서 제일 왼쪽에 있는 점은 LL이라고 하자.

1) LCA(L, X)가 LCA(LL, X)보다 밑에 있는 경우

-> 아까와 똑같이 LCA(L, X)와 X가 이어지는 것이다

2) LCA(L, X)가 LCA(LL, X)의 ancestor인 경우

-> LCA(L, X)가 X와 이어지는 것은 물론이고, LCA(L, X)가 LCA(L, LL)과 이어지는 것도 고려해주어야 한다.

 

위의 과정을 통해서 X가 뿅 생겨났을때 (answer[Y]의 변화량) = ret을 알 수 있다.

지우는 것은 쉽다.

일단 X를 그냥 제거하고, X를 추가했을 때 answer[Y]의 변화량을 구해준 다음에, 그 값을 빼주면 된다.