2026牛客暑期多校 7—— Problem I.晓美焰的时间线记录（应该使用树上染色来表达归属问题啊）（首先啊，这种图论问题，应该使用这个时间的切片，也就是加入这个节点是否的状态来研究，而不是研究一整张图啊）

题目大意

确定一个值，两个点的什么时候不合法→三个点什么时候合法→。。。）（两个叶子的 LCA ，相当于就是在这个 lca，裂成两条链，如果 x 个叶子的两两 lca 都是这个 lca，那这个树从 lca 这里裂成了 x 个

I - Homura’s Timeline Records (晓美焰的时间线记录)

时间限制： C/C++/Rust/Pascal 2秒，其他语言4秒

空间限制： C/C++/Rust/Pascal 1024 M，其他语言2048 M

特殊判定 (Special Judge)： 是

64位 IO 格式： %lld

题目描述

给定一棵包含 $n$ 个节点的树，根节点为 $1$。树上的边代表时间线的分支，根节点代表所有时间循环的共同起点。

定义节点的深度 (depth) 为从根节点到该节点路径上的边数。没有子节点的节点称为叶子节点，代表一条完整的时间线。

晓美焰以某种未知的顺序 $L_1, L_2, \ldots, L_s$ 体验了每一条完整的时间线（即恰好遍历了每一个叶子节点一次）。

丘比的观察系统按照以下规则为每一个叶子节点 $u$ 记录了一个参考编号 $b_u$：

1. 第一个被体验的叶子节点被分配参考编号 $0$。

2. 对于随后被体验的每一个叶子节点 $u$，系统会在所有之前已经体验过的叶子节点中进行筛选。它会选择一个叶子节点 $v$，使得它们的最近公共祖先的深度 $\operatorname{depth}(\operatorname{LCA}(u,v))$ 尽可能大。

3. 如果有多个叶子节点满足深度最大的条件，系统会选择其中最早被体验的那一个。

4. 系统最终将 $b_u$ 赋值为选出的 $v$。

注：$\operatorname{LCA}(u,v)$ 表示节点 $u$ 和 $v$ 在树上的最近公共祖先。更深的最近公共祖先意味着两条时间线共享更长的因果历史。

现在，给定这棵树以及所有叶子节点的参考编号 $b_u$，请你判断这些编号是否可能由某种合法的叶子节点体验顺序产生。如果存在这样的顺序，请输出任意一种合法的顺序。

输入描述

第一行包含一个整数 $n$ ($1 \le n \le 2\cdot 10^5$)，表示树的节点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示节点 $u$ 和节点 $v$ 之间有一条无向边。保证给定的边构成一棵树。

接下来一行包含一个整数 $s$ ($1 \le s \le n$)，表示以节点 $1$ 为根时叶子节点的数量。

接下来的 $s$ 行，每行包含两个整数 $u$ 和 $b_u$ ($1 \le u \le n$, $0 \le b_u \le n$)，其中 $u$ 是一个叶子节点， $b_u$ 是它的参考编号。

保证： 给出的节点恰好涵盖了以 $1$ 为根的树的所有叶子节点，且每个叶子节点只会出现一次。

注意： 输入中的非零 $b_u$ 值不保证一定是叶子节点的编号（可能包含非法数据）。

输出描述

如果不存在任何合法的叶子节点访问顺序，输出一行 NO。

否则，第一行输出 YES。在第二行输出 $s$ 个整数 $L_1, L_2, \ldots, L_s$，表示一种能够产生该记录的合法叶子节点体验顺序。

输出的序列中，每一个叶子节点必须恰好出现一次。如果有多种合法顺序，输出任意一种即可。

样例

Plaintext

7
1 2
1 3
2 4
2 5
3 6
3 7
4
4 0
5 4
6 4
7 6

Plaintext

YES
4 5 6 7

样例解释

在样例中，叶子节点分别为 $4, 5, 6, 7$。我们来验证输出顺序 4 5 6 7 是否合法：

1. 叶子节点 $4$ 第一个被体验，因此 $b_4 = 0$。

2. 对于叶子节点 $5$，之前唯一体验过的叶子节点是 $4$，因此 $b_5 = 4$。

3. 对于叶子节点 $6$，之前体验过 $4$ 和 $5$。$\operatorname{LCA}(6,4) = 1$，$\operatorname{LCA}(6,5) = 1$。两者与 $6$ 的最近公共祖先深度相同。由于 $4$ 比 $5$ 更早被体验，系统选择较早的 $4$，因此 $b_6 = 4$。

4. 对于叶子节点 $7$，之前体验过 $4, 5, 6$。计算可知：$\operatorname{LCA}(7,6) = 3$，而 $\operatorname{LCA}(7,4) = \operatorname{LCA}(7,5) = 1$。因为节点 $3$ 的深度大于节点 $1$ 的深度，深度最大的是节点 $6$，因此 $b_7 = 6$。

综上所述，产生的结果与输入相符，4 5 6 7 是一个合法的顺序。

思路讲解

（先窄化问题，把整个序列的构建，先看两者这个之间的这个关系）

根据题意，如果对于叶子节点 $u$，它的参考编号 $b_u = v$（$v \neq 0$），这不仅意味着在访问序列中 $v$ 必须排在 $u$ 之前。思考一下：设 $w = \operatorname{LCA}(u, v)$，在以 $w$ 为根的整棵子树中，$v$ 的访问顺序必须满足什么条件，才能在所有已访问的节点里成为“LCA 深度最大”且“出现最早”的那一个？

我们会发现，其实 z，v 是一样的。

两个点的情况考虑完了，我们试试看正过来想，3 个点的情况怎么样合法呢？

你们大概地问了一下这个CZK这道题目怎么做，那么，其实这道题目是这样子的，其实我们也大概想到了一点，就是我们我在纸上写的时候，我想到了这个树上的差分。但是实际上因为它是一个归属问题，所以我们应该进行树上的染色。

我们不难发现，如果题目给出的是一个合法的 B 数组，我们可以把 B 数组当做 parent 数组，比较自然地连出一棵树。如果在这棵树上做 BFS，把从根节点出发的路径涂成它的 ID，（其实不是从根节点出发的路径，而是从这个点出发向上走。因为有一个 parent 数组，我们可以用这个 parent 指针不断地往上走，一直走到被涂到颜色的点。但如果是第一个点的话，那么肯定是一直走到根节点）那么后面的人向上涂色时，第一个必须经过的就是自己 B 数组的值（然后停下来）。他们不能经过其他的值，如果经过其他的值，那么就不行了。

AC代码

源代码

心路历程（WA，TLE，MLE……）