RiseOJ – Hijerarhija

설명

Krešimir has started studying corporate structures, including hierarchies. He
observed employees and their relationships within a company. In this case, we are
only looking at superior–subordinate relationships, meaning relationships where
one employee is directly superior to another employee in the company.
A hierarchy is a structure with $$N$$ employees and $$N - 1$$ superior–subordinate
relationships, where there is one person who is directly or indirectly superior to all employees. In the
observed company, there are also $$N$$ employees and $$N - 1$$ such relationships, but it is not certain whether
this is a valid hierarchy or not.
Krešimir has asked you to help answer this question. He has recorded all the data in his notebook.
Additionally, in his notebook, he will make $$Q$$ permanent changes by reversing one superior–subordinate
relationship such that the subordinate becomes superior to their former superior. After each such change,
it is necessary to answer the same question: is the current state a valid hierarchy?

제약

입력 형식

In the first line, there is a positive integer $$N$$ ( $2 \le N \le 3 \cdot 10^{5}$ ).
In the next $$N - 1$$ lines, for each $$i = 1$$ , 2, . . . , $$N - 1$$ , there is a pair of integers $p_{i}$ and $e_{i}$ ( $1 \le p_{i}$ , $e_{i} \le N$ ,
$p_{i}$ ̸ = $e_{i}$ ), indicating that $p_{i}$ is directly superior to $e_{i}$ .
In the next line, there is a non-negative integer $$Q$$ ( $0 \le Q \le 10^{6}$ ).
In the following $$Q$$ lines, there are pairs $a_{i}$ , $b_{i}$ ( $1 \le a_{i}$ , $b_{i} \le N$ , $a_{i}$ ̸ = $b_{i}$ ). It is guaranteed that at that
moment, $a_{i}$ will either be directly superior to $b_{i}$ or vice versa.
In the test data, it is guaranteed that it will be possible to achieve at least one hierarchy with some
sequence of reversals.

출력 형식

In the next $$Q + 1$$ lines, for each of the given scenarios, it is necessary to output whether the current
structure is a hierarchy, i.e., "DA" if it is, or "NE" if it is not (without quotation marks).

서브태스크

서브태스크	점수	설명
1	7점	$N \le 300$ , $$Q = 0$$
2	12점	N, $Q \le 300$
3	16점	N, $Q \le 1000$
4	15점	$$Q = 0$$
5	23점	For each $$i = 1$$ , 2, . . . , $$N - 1$$ , it will hold that $$i$$ is directly superior to $$i + 1$$ or vice versa.
6	17점	No additional constraints.

예제 1

입력

출력

DA
DA
DA
DA

예제 2

입력

출력

DA
NE
DA
DA
NE

문제 정보

생성자가 기록되지 않았습니다.

출처 COCI 2024/2025 Contest 1

올림피아드 > COCI > 2024/2025 > Contest 1

Hijerarhija

평가 및 의견

풀이 제출

서브태스크	점수	설명
1	7점	$N \le 300$ , $\(Q = 0\)$
2	12점	N, $Q \le 300$
3	16점	N, $Q \le 1000$
4	15점	$\(Q = 0\)$
5	23점	For each $\(i = 1\)$ , 2, . . . , $\(N - 1\)$ , it will hold that $\(i\)$ is directly superior to $\(i + 1\)$ or vice versa.
6	17점	No additional constraints.