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

题目背景

译自 COCI 2024/2025 #1 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}$。

输入输出样例 #1

输入 #1

3
1 2
1 3
3
1 2
1 2
1 3

输出 #1

DA
DA
DA
DA

输入输出样例 #2

输入 #2

4
2 1
2 3
1 4
4
4 1
4 1
3 2
1 4

输出 #2

DA
NE
DA
DA
NE

说明/提示

对于 $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$			$12$
$3$	$10^3$		$16$
$4$	$3\times 10^5$	A	$15$
$5$		B	$23$
$6$			$17$

• 特殊性质 A：$m=0$。
• 特殊性质 B：对于 $\forall 1\le i\lt n$，$(i,i+1)$ 间有父子关系。

• #5695. 「COCI 2024/2025 #1」Hijerarhija

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #1 T3「Hijerarhija」

Krešimir 开始研究企业结构，包括层级制度。他观察了公司内部的员工及其关系。在这里，我们只关注上下级关系，即一名员工直接隶属于另一名员工的关系。

层级制度是一个拥有 $N$ 名员工和 $N-1$ 个上下级关系的结构，其中有一人直接或间接领导公司内所有员工。在被观察的公司中，也有 $N$ 名员工和 $N-1$ 个此类关系，但不确定这是否是一个合法的层级结构。

Krešimir 请你帮忙回答这个问题。他已将所有数据记录在笔记本中。此外，他会在笔记本中进行 $Q$ 次永久性变更，通过反转某一个上下级关系，使得下属变为其前上司的上司。在每次此类变更之后，都需要回答同一个问题：当前状态是否是一个合法的层级结构？

输入格式

第一行是一个正整数 $N$ $(2 \leq N \leq 3 \cdot 10^{5})$。

在接下来的 $N-1$ 行中，对于每个 $i=1, 2, \ldots, N-1$，有一对整数 $p_{i}$ 和 $e_{i}$ $(1 \leq p_{i}, e_{i} \leq N, p_{i} \neq e_{i})$，表示 $p_{i}$ 直接领导 $e_{i}$。

下一行是一个非负整数 $Q$ $(0 \leq Q \leq 10^{6})$。

在接下来的 $Q$ 行中，有若干对 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i})$。保证在那个时刻，$a_{i}$ 必定直接领导 $b_{i}$，或者反之。

测试数据保证通过某种反转序列至少可以实现一种层级结构。

输出格式

在接下来的 $Q+1$ 行中，对于给定的每个场景，如果当前结构是一个层级结构，则输出 DA；如果不是，则输出 NE。

样例 1

输入

3
1 2
1 3
3
1 2
1 2
1 3

输出

DA
DA
DA
DA

样例 2

输入

4
2 1
2 3
1 4
4
4 1
4 1
3 2
1 4

输出

DA
NE
DA
DA
NE

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$N \leq 300, Q=0$
$2$	$12$	$N, Q \leq 300$
$3$	$16$	$N, Q \leq 1000$
$4$	$15$	$Q=0$
$5$	$23$	对于每个 $i=1, 2, \ldots, N-1$，保证 $i$ 直接领导 $i+1$ 或反之
$6$	$17$	无附加限制