트리와 띄엄띄엄쿼리 & 루트가 많은 트리?

https://jungol.co.kr/problem/8663

트리와 띄엄띄엄쿼리 · Silver II

 

트리에서 한 정점으로 부터 거리가 홀수, 또는 짝수인 정점에 특정 작업을 해주어야 하는 문제 유형이다.

처음에는 하나의 노드에서 매번 dfs를 돌려서 거리가 짝수인 곳에만 작업을 수행하도록 할 계획이었다.  하지만, 노드 개수 30만에

쿼리 개수 30만이라는 것을 보고 완전탐색은 아니라는 것을 그제야 깨달았다.

 

그렇다면 한 정점으로 부터 거리가 짝수 또는 홀수인 정점들에 작업을 한꺼번에 수행하는 것이 O(1) 밖에 안걸린다는건데...

어떻게 하지??

 

이 생각을 하고 그대로 막혀버렸다. 정올반 선생님의 해설을 듣고서야 더 쉬운 방법이 있다는 것을 깨달았다.

결론 부터 말하자면 루트 노드에서 모든 정점까지의 거리를 딱 한번만 구해주면 된다.

정확히는 루트노드와의 거리가 홀수인 것과 짝수인 것을 각각 다른 색깔로 색칠해주면 된다.

 

이때, 색깔이 같은 두 노드는 짝수 거리만에 이동할 수 있다.

 

각 노드에서 루트노드까지의 거리를 a, b라고 하고, 두 노드가 공유하는 최소공통조상에서 루트노드까지의 거리를 x라고 하면 

두 노드 사이의 거리는 a + b - 2x이다.

이때, 2x는 반드시 짝수이므로 a+b만 짝수이면 되는 것이다. 

때문에, 루트 노드까지의 홀짝성이 같은 노드는 짝수거리만에 이동할 수 있기에, 홀수배열, 짝수 배열을 따로 만든 후, 

작업을 수행할 때는 (해당 문제에서는 노드에 가중치에 값을 더해줄 때) 홀수에만, 짝수에만 한꺼번에 해주면 되는 것이다.

 

트리의 성질을 이용하여 문제를 간단하게 바꾸는 방법을 배워간 문제이다.....(반성) 

 

 

https://www.biko.kr/problem/1784

무료 프로그래밍 학습 플랫폼 BIKO

 

진짜 진짜 진짜 레전드 문제....

 

우선 트리의 유우우우명한 특징 하나!

일반적인 트리의 모든 노드는 루트노드가 될 수 있다!

 

하지만 이 문제에서는 루트노드 조금 다르게 정의하고 있다. 간선에 방향이 있을 때 어떤노드에서 시작해서 모든 정점을 방문할 수 있을 때 그 노드를 루트노드로 정의하는 것이다.

 

입력으로 주어지는 트리에서는 방향이 있는 간선과 없는 간선이 모두 존재한다.

 

여기서 조금 어려워진다.

 

 

우리는 트리에서 루트노드가 존재할 조건을 생각해봐야한다. 

만약 주어진 입력에서 모든 간선에 방향이 존재한다고 해보자.

 

 이 문제의 정의에 따라 루트노드에서 시작하여 '모든' 정점을 방문할 수 있어야 한다. 때문에, 진입차수가 0인 정점은 단 한개여야 한다.

때문에, 이 경우에는 진입차수가 0인 간선이 단 한개 존재해야지만 루트노드가 존재할 수 있다.

 

 

하지만 주어지는 입력에서는 방향이 없는 간선도 존재한다.

우리는 여기서 위에서 언급한 '무방향 트리에서 모든 노드가 루트가 될 수 있다'는 성질을 이용할 수 있다.

 

방향이 주어지지 않은 간선으로 연결된 노드들에 대해서는 자유롭게 움직일 수 있기 때문에, 분리집합으로 묶어서 하나의 컴포넌트로 보는 것이다. 

 

때문에, 우리는 각 컴포넌트에 대해서 진입, 진출 차수를 계산하여 위 조건에 위배되지 않는다면 진입차수가 0인 컴포넌트의 원소의 개수를 출력해주면 된다.

 

구현은 생각보다 까다로우니 나중에 다시 짜봐야겠다.