Count

시간 제한6초메모리 제한2048 MB

요약

루트가 있는 트리에서 정점 u로부터 거리 d 이내에 있는 정점끼리 이어진 간선 집합을, R과 C 호출을 M번 이하로 써서 만드는 문제입니다.

난이도: 어려움10점 중 9점
유형: 트리, 분할 정복, 동적 계획법
정답자: 아직 제출이 없습니다

문제

이 문제는 대화형 문제이다.

5중항 $(T, I, S_V, S_E, \iota)$ 가 주어진다.

$T$ 는 정점이 $n$ 개인 루트 트리 $T = (V, E)$ 이다. $V$ 는 정점 집합, $E$ 는 간선 집합이다. 정점에는 $1, 2, \ldots, n$ 의 번호가 붙어 있고, 루트는 1번 정점이다.
$I$ 는 정보들의 집합이다. 특별한 원소가 두 개 있는데, 항등원 $\epsilon$ 과 불법 원소 $\perp$ 이다. 일반 정보는 정점 집합과 간선 집합이라는 두 속성을 가진다. 항등원은 간선 집합 속성만 가진다. 불법 원소는 두 속성이 모두 없다.
일반 정보 $o \in I \setminus \{\epsilon, \perp\}$ 의 정점 집합 $S_V(o)$ 는 $V$ 의 원소 2개짜리 부분집합이다. 즉 $S_V(o) \subseteq V$ 이고 $|S_V(o)| = 2$ 이다.
$o \in I \setminus \{\perp\}$ 의 간선 집합 $S_E(o)$ 는 $E$ 의 부분집합이다. 항등원의 간선 집합은 공집합이다. 즉 $S_E(\epsilon) = \emptyset$ 이다.
트리의 모든 간선 $e = (u, v) \in E$ 에 대해 정보 $\iota(e) \in I$ 가 있다. 이 정보의 정점 집합은 $\{u, v\}$ 이고 간선 집합은 $\{e\}$ 이다. 즉 $S_V(\iota(e)) = \{u, v\}$ , $S_E(\iota(e)) = \{e\}$ 이다.

정보를 결합하는 연산은 $R$ 과 $C$ 두 가지이다. 모든 $a, b \in I$ 에 대해 $r = R(a, b)$ , $c = C(a, b)$ 라 하면 $r, c \in I$ 이다.

$a = \epsilon$ 이면 $r = c = b$ 이다. $b = \epsilon$ 이면 $r = c = a$ 이다.
$a = \perp$ 이거나 $b = \perp$ 이면 $r = c = \perp$ 이다.
나머지 경우에 $S_E(a) \cap S_E(b) \neq \emptyset$ 이거나 $|S_V(a) \cap S_V(b)| \neq 1$ 이면 $r = c = \perp$ 이다.
그 밖의 경우에는 $S_E(r) = S_E(c) = S_E(a) \cup S_E(b)$ , $S_V(r) = S_V(a)$ , $S_V(c) = S_V(a) \oplus S_V(b)$ 이다. 여기서 $\oplus$ 는 대칭차이고, $A \oplus B = (A \cup B) \setminus (A \cap B)$ 이다.

트리 $T$ 에서 두 정점 사이의 거리는 두 정점을 잇는 유일한 단순 경로가 지나는 간선의 수이다.

질의가 $q$ 개 주어진다. 각 질의는 정점 $u$ 와 음이 아닌 정수 $d$ 로 이루어진다. $X$ 는 $u$ 까지의 거리가 $d$ 이하인 정점들의 집합이다. $Y = \{(a, b) \in E \mid a, b \in X\}$ 는 양 끝점이 모두 $X$ 에 속하는 간선들의 집합이다.

$\epsilon$ 과 모든 $\iota(e)$ ( $e \in E$ )에서 출발해 유한 번의 $R$ , $C$ 호출로 $o \neq \perp$ 이고 $S_E(o) = Y$ 인 정보 $o$ 를 만들 수 있다는 것이 증명되어 있다. 특히 $d = 0$ 이면 출력은 항등원 $\epsilon$ 이어야 한다.

각 질의마다 위 조건을 만족하는 정보 $o$ 를 만들어야 하며, $R$ 과 $C$ 호출 횟수의 합은 $M$ 을 넘을 수 없다.

제한

모든 테스트 케이스에 대해 $1 \leq n \leq 2 \times 10^5$ , $1 \leq q \leq 10^6$ 이다. 각 질의에 대해 $1 \leq u \leq n$ , $1 \leq d \leq n-1$ 이다.

테스트 케이스	$n=$	$q=$	속성	$M=$
$1$	$1000$	$10^4$		$500$
$2$	$2000$	$10^4$		$500$
$3,4$	$10^5$	$10^6$	A	$5$
$5,6$	$6 \times 10^4$	$6\times 10^4$	B	$50$
$7$	$6 \times 10^4$	$6 \times 10^4$	B	$5$
$8$	$10^5$	$10^5$	B	$5$
$9$	$7500$	$5 \times 10^4$	C	$500$
$10$	$10^4$	$5 \times 10^4$		$500$
$11$	$1.5 \times 10^4$	$5 \times 10^4$		$500$
$12$	$2 \times 10^4$	$5 \times 10^4$		$50$
$13$	$2.5 \times 10^4$	$5 \times 10^4$		$5$
$14$	$3 \times 10^4$	$10^5$		$5$
$15$	$6 \times 10^4$	$10^6$	D	$5$
$16$	$6 \times 10^4$	$10^6$		$5$
$17$	$8 \times 10^4$	$10^6$		$5$
$18$	$10^5$	$10^6$		$5$
$19$	$1.5 \times 10^5$	$10^6$		$5$
$20$	$2 \times 10^5$	$10^6$		$1$

속성 A: 모든 $i = 1, 2, \ldots, n-1$ 에 대해 $i+1$ 의 부모는 $i$ 이다.
속성 B: 모든 질의에서 $u = 1$ 이다.
속성 C: 모든 질의에서 $d \leq 100$ 이다.
속성 D: 모든 질의에서 $d \geq 1000$ 이다.

예제1

예제 1
입력
```
2
1 2
1
2 1
```
예상 출력
```
1 2
```