경로 임베딩

정점 수가 같은 게스트 그래프 G와 호스트 그래프 H가 주어졌을 때, 그래프 임베딩 문제는 G의 정점 집합 V(G)에서 H의 정점 집합 V(H)로의 일대일 대응 σ와, G의 간선 집합 E(G)의 각 간선을 H의 경로에 대응시키는 사상을 찾는 것이다. 여러 응용 문제를 그래프 임베딩으로 모델링할 수 있다. 특히 그래프 임베딩은 오래전부터 병렬 알고리즘을 병렬 구조에 배치하는 문제를 모델링하는 데 쓰여 왔다.

임베딩의 품질은 여러 비용 기준으로 측정한다. 그중 dilation은 G의 모든 간선이 대응되는 경로 길이의 최댓값이다. 호스트 그래프 H가 임의의 두 정점을 유일한 경로로 연결하는 트리라면, G의 간선 (u, v)는 H에서 σ(u)와 σ(v)를 잇는 유일한 경로에 반드시 대응된다. 따라서 그래프 G에서 트리 H로의 임베딩 σ의 dilation은 max(u,v)𝜖E(G) d**H(σ(u), σ(v))로 간단히 나타낼 수 있다. 여기서 d**H(σ(u), σ(v))는 H에서 σ(u)와 σ(v) 사이의 거리이다. 아래 Figure H.1에 나온 임베딩의 dilation은 3이다.

\n Figure H.1: 정점이 12개인 경로 그래프를 정점이 12개인 트리에 임베딩한 σ. σ는 두 줄 표기법 (\begin{pmatrix} 1 & 2 &3&4&5&6&7&8&9&10&11&12 \ 7&6&5&4&1&2&3&8&9&11&12&10 \end{pmatrix})로 쓸 수 있으며, 이는 σ(1) = 7, σ(2) = 6, σ(3) = 5, …, σ(12) = 10을 뜻한다.

이 문제는 경로 그래프를 트리에 임베딩하는 문제를 다룬다. 경로 그래프는 리프가 많아야 두 개인 트리이다. 경로 그래프를 트리에 임베딩한 결과가 주어졌을 때, 그 임베딩의 dilation을 구하는 효율적인 프로그램을 작성하라.

프로그램은 표준 입력에서 데이터를 읽는다. 첫째 줄에는 트리를 이루는 호스트 그래프 H의 정점 수 n이 주어진다. 여기서 2 ≤ n ≤ 100,000이다. 이어서 n − 1개의 줄이 주어지고, 각 줄에는 H의 정점 u와 정점 v 사이의 간선을 나타내는 두 양의 정수 u, v가 있다. 정점 번호는 1부터 n까지이다. 마지막 줄에는 H의 정점을 나열한 순서 σ(1), σ(2), …, σ(n)가 주어지며, 이는 경로 그래프 G를 H에 임베딩한 결과이다. 여기서 V(G) = {1, 2, … , n}이고 E(G) = {(u, v) ∶ v = u + 1}이다.

프로그램은 표준 출력에 결과를 쓴다. 정수 하나를 한 줄에 정확히 출력한다. 주어진 임베딩의 dilation이 3 이하이면 그 dilation을 출력하고, 그렇지 않으면 99를 출력한다.