Rooted Subtrees
시간 제한11초메모리 제한512 MB
두 루트 r과 p가 주어질 때, r을 루트로 하는 트리의 서브트리와 p를 루트로 하는 트리의 서브트리의 교집합으로 만들 수 있는 서로 다른 공집합이 아닌 집합의 개수를 구한다.
문제
트리는 n개의 노드와 n − 1개의 간선으로 이루어진 연결된 비순환 무방향 그래프다. 임의의 두 노드 사이에는 정확히 하나의 경로가 존재한다. 루트 있는 트리는 트리에서 한 노드를 루트로 선택한 것이다.
T를 트리, Tr을 T를 노드 r을 루트로 하여 만든 트리라고 하자. Tr에서 u의 서브트리는 r에서 v로 가는 경로가 u를 포함하는 모든 노드 v의 집합이다(u 자신도 포함). 이 문제에서 루트가 r인 트리에서 u의 서브트리에 속하는 노드 집합을 Tr(u)로 표기한다.
q개의 쿼리가 주어진다. 각 쿼리는 두 개의 노드 r과 p(서로 같을 수도 있다)로 이루어진다. 집합 S가 “얻을 수 있다”는 것은 루트가 r인 트리의 서브트리와 루트가 p인 트리의 서브트리의 교집합으로 표현될 수 있다는 것이다. 형식적으로, S = Tr(u) ∩ Tp(v)인 노드 u, v가 존재하면 S는 “얻을 수 있다”.
주어진 루트 쌍에 대해, 공집합이 아니면서 얻을 수 있는 서로 다른 집합의 개수를 세어라. 두 집합이 다르다는 것은 한쪽에만 속하는 원소가 존재한다는 것이다.
입력
첫 줄에는 공백으로 구분된 두 정수 n과 q가 주어진다(1 ≤ n, q ≤ 2 · 105). n은 트리의 노드 수, q는 답해야 할 쿼리의 수이다. 노드는 1부터 n까지 번호가 매겨진다.
다음 n − 1개의 줄에는 각각 공백으로 구분된 두 정수 u와 v가 주어진다(1 ≤ u, v ≤ n, u ≠ v). 이는 노드 u와 v 사이의 무방향 간선을 나타낸다. 이 간선 집합이 올바른 트리를 이룸이 보장된다.
다음 q개의 줄에는 각각 공백으로 구분된 두 정수 r과 p가 주어진다(1 ≤ r, p ≤ n). 이는 해당 쿼리의 루트 노드이다.
출력
각 쿼리마다 위 절차로 만들 수 있는 서로 다른 얻을 수 있는 노드 집합의 개수를 한 줄에 하나씩 출력한다.
힌트
첫 번째 트리에서 가능한 루트 선택은 다음과 같다.
1과 3을 루트로 할 때, 8개의 얻을 수 있는 집합은 다음과 같다.
- u = 1, v = 1을 선택한 {1},
- u = 1, v = 2를 선택한 {1, 2, 4, 5},
- u = 1, v = 3을 선택한 {1, 2, 3, 4, 5},
- u = 2, v = 3을 선택한 {2, 3, 4, 5},
- u = 2, v = 2를 선택한 {2, 4, 5},
- u = 3, v = 3을 선택한 {3},
- u = 2, v = 4를 선택한 {4, 5},
- u = 5, v = 5를 선택한 {5}.
대신 4와 5를 루트로 하면 얻을 수 있는 집합은 6개뿐이다.
- u = 1, v = 1을 선택한 {1},
- u = 2, v = 4를 선택한 {1, 2, 3},
- u = 4, v = 4를 선택한 {1, 2, 3, 4},
- u = 4, v = 5를 선택한 {1, 2, 3, 4, 5},
- u = 3, v = 2를 선택한 {3},
- u = 5, v = 5를 선택한 {5}.
이 중 일부는 같은 집합에 도달하는 다른 u, v 선택이 존재한다.