P11389 [COCI 2024/2025 #1] 等级 / Hijerarhija

译自 [COCI 2024/2025 #1](https://hsin.hr/coci/) T3。$\texttt{3s,0.5G}$。满分为 $90$。

有 $n$ 个节点，给定 $(n-1)$ 对点之间的父子关系。 有 $m$ 个修改，每次给定一对父子，将它们的关系反转（即，原来的父亲变成儿子，儿子变成父亲）。 在第一次修改前，和每次修改后，输出这张图是否是一棵有根树。

第一行，一个正整数 $n$。 接下来 $(n-1)$ 行，每行两个正整数 $u,v$，表示 $u$ 是 $v$ 的父亲。 接下来一行，一个正整数 $m$。 接下来 $m$ 行，每行两个正整数 $u,v$，表示一次修改。保证 $u,v$ 是父子关系。

输出 $(m+1)$ 行： 在对应时刻，若是有根树，输出 $\texttt{DA}$（克罗地亚语「是」）；否则输出 $\texttt{NE}$（克罗地亚语「否」）。 **保证至少有一个回答是 $\texttt{DA}$**。

对于 $100\%$ 的数据，保证： - $2\le n\le 3\times 10^5$； - $0\le m\le 10^6$； - $1\le u,v\le n$，$u\neq v$。 - **至少有一个回答是 $\texttt{DA}$**。 | 子任务编号 | $n,m\le$ | 特殊性质 | 得分 | | :--: | :--: | :--: |:--: | | $ 1 $ | $300$ | A | $ 7 $ | | $ 2 $ | $300$ | | $ 12 $ | | $ 3 $ | $10^3$ | | $ 16 $ | | $ 4 $ | $3\times 10^5$ | A | $ 15 $ | | $ 5 $ | $3\times 10^5$ | B | $ 23 $ | | $ 6 $ | $3\times 10^5$ | | $ 17 $ | - 特殊性质 A：$m=0$。 - 特殊性质 B：对于 $\forall 1\le i\lt n$，$(i,i+1)$ 间有父子关系。