P10787 [NOI2024] 树的定向

由于评测机性能差异，原题时限为 3s，洛谷上时限为 6s。

给定一棵含有 $n$ 个顶点的树，顶点从 $1$ 到 $n$ 编号，树上第 $i(1\leq i\leq n-1)$ 条边连接顶点 $u_i$ 和 $v_i$。 现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $n-1$ 的字符串 $S=s_1s_2\ldots s_{n-1}$ 来描述。其中 $s_i=0$ 代表第 $i$ 条边定向为 $u_i \to v_i$，否则 $s_i=1$ 代表第 $i$ 条边定向为 $v_i\to u_i$。 给定 $m$ 个顶点对 $(a_i,b_i)$，其中 $1\leq a_i,b_i \leq n$ 且 $a_i\neq b_i$。 一个**完美定向**定义为：在此定向下，对于任意 $1\leq i\leq m$，$a_i$ ****不能到达**** $b_i$。 试求在所有完美定向中，所对应的字符串字典序最小的定向。**数据保证存在至少一个完美定向**。 定义字符串 $S=s_1s_2\ldots s_{n-1}$ 的字典序小于 $T=t_1t_2\ldots t_{n-1}$ 若存在一个下标 $k$ 使得 $s_1=t_1, s_2=t_2, \ldots, s_{k-1}=t_{k-1}$ 且 $s_k < t_k$。

无

无

**【样例 1 解释】** 在该样例中，若 $S=000$，则该定向中 $1$ 能到达 $4$（存在路径 $1\to 2\to 3\to 4$），因而不是完美定向。若 $S=001$，则该定向中 $3$ 不能到达 $2$，$1$ 不能到达 $4$，因面是完美定向。故答案为 $001$。 **【样例 2 解释】** 在该样例中，一组完美定向必定满足 $4$ 不能到达 $3$，$5$ 不能到达 $1$。故 $s_1=s_5=1$。若 $s_2=s_3=0$，则存在路径 $1\to 2\to 3\to 4$，故 $1$ 可到达 $4$。故其不是完美定向。因此，所有完美定向必定满足 $S$ 的字典序不小于 $10101$。且容易验证 $S=10101$ 时，对应的定向是完美定向。 **【数据范围】** 对于所有测试数据保证 $2\leq n\leq 5\times 10^5$，$1\leq m\leq 5\times 10^5$，$1\leq u_i,v_i\leq n$ 且所有的边构成了一棵树，$1\leq a_i,b_i \leq n$ 且 $a_i\neq b_i$。 数据保证存在至少一个完美定向。 | 测试点编号 | $n$ | $m$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1\sim 3$ | $\leq 15$ | $\leq 50$ | 无 | | $4\sim 6$ | $\leq 300$ | $\leq 300$ | 无 | | $7,8$ | $\leq 400$ | $=(n-1)(n-2)$ | A | | $9,10$ | $\leq 2\,000$ | $\leq 2\,000$ | B | | $11\sim 14$ | $\leq 2\,000$ | $\leq 2\,000$ | 无 | | $15,16$ | $\leq 10^5$ | $\leq 10^5$ | B | | $17,18$ | $\leq 10^5$ | $\leq 10^5$ | 无 | | $19\sim 21$ | $\leq 2\times 10^5$ | $\leq 2\times 10^5$ | 无 | | $22\sim 25$ | $\leq 5\times 10^5$ | $\leq 5\times 10^5$ | 无 | - 特殊性质 A：保证 $(a,b)$ 出现在 $(a_i,b_i)$ 中当且仅当 $a\neq b$ 且 $a,b$ 在树上不相邻。 - 特殊性质 B：保证树上编号为 $1$ 的顶点与其他每个顶点均相邻。