4015. [NOI 2024]树的定向

【题目描述】

给定一棵含有 $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$。

【输入格式】

输入的第一行包含三个非负整数 $c,n,m$，分别表示测试点编号，树的点数，顶点对的个数。其中 $c=0$ 表示该测试点为样例。

接下来 $n-1$ 行，每行包含两个正整数 $u_i,v_i$ 表示树的一条边。保证 $1\leq u_i,v_i\leq n$ 且这 $n-1$ 条边构成了一棵树。

接下来 $m$ 行，每行包含两个正整数 $a_i,b_i$。保证 $1\leq a_i,b_i \leq n$ 且 $a_i\neq b_i$。

【输出格式】

输出一行包含一个字符串 $S=s_1s_2\ldots s_{n-1}$，表示字典序最小的完美定向所对应的 $01$ 字符串。

【样例1输入】

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

【样例1输出】

001

【样例2输入】

0 6 8
5 1
2 3
1 2
5 6
4 3
4 3
5 1
6 3
5 4
1 4
5 2
3 6
6 2

【样例2输出】

10101

【样例3~6】

样例下载

样例3满足测试点 1-3 的约束条件。

样例4满足测试点 4-6 的约束条件。

样例5满足测试点 7,8 的约束条件。

样例6满足测试点 9,10 的约束条件。

【样例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$。

数据保证存在至少一个完美定向。

· 特殊性质 A：保证 $(a,b)$ 出现在 $(a_i,b_i)$ 中当且仅当 $a\neq b$ 且 $a,b$ 在树上不相邻。

· 特殊性质 B：保证树上编号为 $1$ 的顶点与其他每个顶点均相邻。

【来源】

NOI2024 Day1 Task3