UOJ Logo Universal Online Judge

UOJ

#895. 【NOI2024】树的定向

附件下载 统计

给定一棵含有 n 个顶点的树,顶点从 1n 编号,树上第 i(1in1) 条边连接顶点 uivi

现在,我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 n1 的字符串 S=s1s2sn1 来描述。其中 si=0 代表第 i 条边定向为 uivi,否则 si=1 代表第 i 条边定向为 viui

给定 m 个顶点对 (ai,bi),其中 1ai,binaibi

一个完美定向定义为:在此定向下,对于任意 1imai 不能到达 bi

试求在所有完美定向中,所对应的字符串字典序最小的定向。数据保证存在至少一个完美定向

定义字符串 S=s1s2sn1 的字典序小于 T=t1t2tn1 若存在一个下标 k 使得 s1=t1,s2=t2,,sk1=tk1sk<tk

输入格式

输入的第一行包含三个非负整数 c,n,m,分别表示测试点编号,树的点数,顶点对的个数。其中 c=0 表示该测试点为样例。如果你要提交 hack 数据,请你保证 c=0

接下来 n1 行,每行包含两个正整数 ui,vi 表示树的一条边。保证 1ui,vin 且这 n1 条边构成了一棵树。

接下来 m 行,每行包含两个正整数 ai,bi。保证 1ai,binaibi

输出格式

输出一行包含一个字符串 S=s1s2sn1,表示字典序最小的完美定向所对应的 01 字符串。

样例一

input

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

output

001

explanation

在该样例中,若 S=000,则该定向中 1 能到达 4(存在路径 1234),因而不是完美定向。若 S=001,则该定向中 3 不能到达 21 不能到达 4,因面是完美定向。故答案为 001

样例二

input

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

output

10101

explanation

在该样例中,一组完美定向必定满足 4 不能到达 35 不能到达 1。故 s1=s5=1。若 s2=s3=0,则存在路径 1234,故 1 可到达 4。故其不是完美定向。因此,所有完美定向必定满足 S 的字典序不小于 10101。且容易验证 S=10101 时,对应的定向是完美定向。

样例三

见附件下载中的 ex_tree3.inex_tree3.ans

这个样例满足测试点 13 的约束条件。

样例四

见附件下载中的 ex_tree4.inex_tree4.ans

这个样例满足测试点 46 的约束条件。

样例五

见附件下载中的 ex_tree5.inex_tree5.ans

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

样例六

见附件下载中的 ex_tree6.inex_tree6.ans

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

数据范围

对于所有测试数据保证 2n5×1051m5×1051ui,vin 且所有的边构成了一棵树,1ai,binaibi

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

测试点编号 n m 特殊性质
13 15 50
46 300 300
7,8 400 =(n1)(n2) A
9,10 2000 2000 B
1114
15,16 105 105 B
17,18
1921 2×105 2×105
2225 5×105 5×105
  • 特殊性质 A:保证 (a,b) 出现在 (ai,bi) 中当且仅当 aba,b 在树上不相邻。
  • 特殊性质 B:保证树上编号为 1 的顶点与其他每个顶点均相邻。

时间限制:3s6s

空间限制:2GB