apio 2010 patrol 간략한 풀이

우선 K=1일때에는 트리의 지름에 설치하는것이 가장최적이라는 결론을 내릴수 있는데 

그에 대한 증명을 위해서 지름길을 설치했을때의 경로길이를 수식으로 표현해보자

일단 지름길을 설치하지 않았을때에는 모든간선을 2번씩 지나야함으로 

경로이길이는 2(N-1)이 된다.

지름길을 하나 설치하면 트리에 간선을 하나 추가하는 행위임으로 반드시 하나의 사이클이 생기게된다.

이때 사이클 위에 존재하는 간선은 한번씩만 사이클위에 속하지 않는 간선은 2번씩지나야함으로

경로의 길이는 2(N-1) - L + 1이 되는데 L은 (사이클 위에 포함된 정점의 갯수-1)개 이다.

따라서 K=1일때는 간선을 추가하여 만드는 사이클의 길이(즉, 정점갯수-1) 가 최대가 되게 하면 됨으로 

트리에 지름에 설치하는것이 가장 최적이라는 결과가 나온다.

이제 K=2일때 생각을 해보자

우리가 설치할 두개의 지름길에 따라서 생기는 사이클의 갯수도 2개가 된다.

이때 두개의 사이클이 하나이상의 엣지를 공유하는경우(같은 정점을 공유하는것은 상관없다)와 

엣지를 공유하지 않는경우로 생각할수 있는데

엣지를 공유하지 않는경우에는 트리에서 두개의 경로의합이 가장크게 하는 정점을 찾으면 된다.

그러면 엣지를 서로 공유하는 경우가 문제가되는데, 이는 두개의 경로를 조금만 변형시켜주면 서로 엣지를 공유하지 않도록 바꿀수있다

즉 (v1,v2)를 연결하는 지름길 e1 과 (v3,v4)를 연결하는 지름길 e2를 

1. (v1,v3)와 (v2,v4)로 연결하거나

2. (v1,v4)와 (v2,v3)로 연결하면

두개중 하나의 경우에서는 반드시 겹치는 경로가 사라지게 된다.

즉 K=2일때에는 트리에서 두개의 경로의합이 최대가되는 경로 2개만 찾으면된다.

이사실을 알았을때

K=1일때와 K=2일때 해결하는방법을 알아보자

i) K=1일때

간단한 트리DP로 해결가능하다

H[u] = u와 u의 자식간의 가장 긴 경로의 길이(끝점중 하나가 u라는뜻); 로 정의하면 O(N)만에 해결할수 있을것이다.

ii) K=2일때

K=1일때보다는 조금 복잡하지만 여전히 트리 DP로 해결하다.

우선 구현에 사용되는 DP table정의를 모두 적어보면 다음과 같다.

H[u] = u와 u의 자식간의 가장 긴 경로의 길이(끝점중 하나가 u라는뜻)

L[u] = u의 서브트리들중에서 u를 포함한 가장긴 경로의 길이

A[u] = u의 서브트리들중에서 가장긴 경로의 길이

B[u] = u의 서브트리들중에서 엣지가 서로 곂치지 않는 서로다른 두개의 경로의 길이의 최대합

       이때 두개의 경로를 P,Q라고 하자, P 경로의 끝점은 반드시 u 가 되어야함.

D[u] = u의 서브트리들중에서 서로 곂치지않는 경로2개의 길이의 최대합

H[u]는 트리 순회하면서 O(N)만에 가능

L[u]는 H[u]를 이용해서 O(N)만에 가능

A[u]는 L[u]를 이용해서 O(N)만에 가능 

B[u]는 그냥 하면 O(N^2) 이되는데 잘하면 O(N)으로 가능하다

D[u]도 그냥 하면 O(N^2) 이되는데 잘하면 O(N)으로 가능하다

*B[u]와 D[u] 잘 계산하는방법*

B[u]는 세가지 경우로 나눌수있는데

1. 두개의 경로 P,Q가 모두 정점 u를 포함하는경우 (단 P의 끝점은 u)

   이때 B[u]는  u의 자식정점을 CH(u)라고 정의할때 H[CH(u)]의 최댓값3개의 합이다.

2. 두개의 경로 P,Q가 있는데 u의 자식들중 임의로 하나를 v 라고하자 이때 경로 P는 edge(u,v)를 포함하는경로이고

   Q는 v의 서브트리에 완전히 포함되는 가장긴 경로이다. 이때는 B[u] = B[v] + 1

3. 두개의 경로 P,Q가 있는데 u의 자식들중 임의로 두개를 v,w라고 하자 이때 경로 P는 edge(u,v)를 포함하는 경로이고

   Q는 w의 서브트리에 완전히 포함되는 가장긴 경로이다. B[u] = H[v] + A[w] + 1;

D[u]도 세가지 경우로 나눌수 있는데

1. 두개의 경로 P,Q가 모두 u를 포함하는경우 , u의 자식을 CH(u)라고 할때 D[u] = H[CH(u)]의 최댓값 두개의 합 + 2

2. 두개의 경로 P,Q모두 u를 포함하지 않는경우 , u의 자식을 CH(u)라고 할때 D[u] = A[CH(u)]의 최댓값 두개의 합

3. 두개의 경로 P,Q중 하나만 u를 포함하는경우 , D[u] = B[u];

따라서 총 시간복잡도는 O(N)이 된다.