11174: NOI2024 - D1T3 树的定向
[Creator : ]
Description
给定一棵含有 $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$。
现在，我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为 $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$。
Input
输入的第一行包含三个非负整数 $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$。
接下来 $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$。
Output
输出一行包含一个字符串 $S=s_1s_2\ldots s_{n-1}$，表示字典序最小的完美定向所对应的 $01$ 字符串。
Constraints
对于所有测试数据保证 $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$。
数据保证存在至少一个完美定向。
数据保证存在至少一个完美定向。
Sample 1 Input
0 4 2
1 2
2 3
3 4
3 2
1 4
Sample 1 Output
001
在该样例中，若 $S=000$，则该定向中 $1$ 能到达 $4$（存在路径 $1\to 2\to 3\to 4$），因而不是完美定向。若 $S=001$，则该定向中 $3$ 不能到达 $2$，$1$ 不能到达 $4$，因面是完美定向。故答案为 $001$。
Sample 2 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
Sample 2 Output
10101
在该样例中，一组完美定向必定满足 $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$ 时，对应的定向是完美定向。
Sample 3 Input
0 13 50
2 12
5 4
1 5
9 1
11 4
3 12
8 12
6 10
7 11
2 1
13 3
6 5
5 3
10 7
11 9
6 7
7 3
11 1
3 9
11 12
6 1
9 11
8 13
1 4
6 2
1 9
10 8
3 12
9 2
13 1
1 8
1 13
6 3
4 13
6 4
9 3
11 2
5 12
3 10
11 8
12 13
12 4
10 4
10 9
4 12
4 2
4 8
3 13
1 12
13 4
11 3
2 11
13 8
10 6
4 1
6 9
5 13
3 1
10 1
6 11
6 13
10 11
Sample 3 Output
001001000001
0 297 298
253 21
145 13
223 172
123 202
214 88
192 206
88 177
113 40
21 113
88 196
196 70
70 37
147 229
270 37
38 96
37 212
113 18
13 230
197 18
13 247
82 272
212 136
136 45
261 13
69 197
257 13
45 208
236 69
294 13
256 89
13 27
26 64
208 163
19 69
103 19
72 163
144 19
72 235
22 175
72 43
43 186
275 144
252 43
13 156
121 192
181 13
201 252
275 150
141 150
13 286
130 128
64 184
167 141
169 229
201 128
132 167
128 54
84 254
44 54
199 167
243 54
102 13
90 243
42 276
29 36
93 199
42 84
176 90
93 63
28 93
25 28
58 25
287 169
161 50
82 73
13 10
170 101
143 25
288 64
260 210
260 143
13 215
134 159
171 260
8 108
13 222
171 248
271 248
13 83
296 159
90 50
6 271
289 271
50 67
289 30
13 127
292 30
249 292
12 67
293 131
249 293
67 124
73 8
110 126
76 124
38 240
109 217
109 76
110 293
46 109
169 251
13 237
240 180
3 123
13 268
2 13
111 46
110 193
191 178
52 240
137 159
105 8
59 193
193 297
153 13
139 297
71 139
178 46
189 13
71 285
232 13
125 178
285 185
185 14
125 216
13 281
125 104
14 23
14 194
258 194
291 13
60 78
203 258
60 104
56 13
187 203
233 170
284 187
91 52
135 187
49 13
224 60
279 224
81 135
205 279
223 22
166 137
146 61
170 13
81 146
146 277
262 277
13 41
164 205
123 200
13 133
95 13
262 218
207 164
66 295
66 207
13 198
140 218
140 273
116 66
273 15
228 13
283 42
80 116
269 13
92 166
168 288
162 273
92 220
31 220
13 118
7 162
85 200
116 117
13 250
250 57
117 9
47 157
100 117
114 239
55 251
7 209
274 13
209 87
55 259
100 114
16 114
105 152
149 16
149 204
168 221
154 283
68 13
119 204
1 221
231 209
13 107
13 129
231 94
13 148
231 75
20 119
263 20
122 75
11 13
290 122
213 13
48 290
173 290
33 79
33 263
155 13
33 24
256 242
266 13
173 278
24 267
256 112
278 65
121 51
77 227
106 31
4 13
226 259
1 86
13 264
241 65
24 77
13 165
13 39
280 77
174 13
282 154
183 280
265 13
51 223
13 35
65 151
13 160
158 105
112 97
238 280
157 85
17 13
98 151
179 98
32 13
282 244
238 219
13 255
13 120
142 13
13 62
182 52
13 53
29 250
179 188
245 219
138 13
34 13
234 188
13 5
234 195
13 219
74 99
13 190
13 74
97 115
223 250
74 211
211 246
225 259
220 3
137 259
211 272
26 244
105 242
234 38
97 229
84 200
271 73
256 89
77 61
179 61
25 28
283 61
215 61
262 277
8 108
267 61
1 221
81 61
223 172
114 281
290 61
179 98
288 61
186 61
135 187
61 215
61 268
210 143
132 61
74 99
230 247
61 153
59 61
116 66
211 61
166 137
133 61
61 160
106 31
266 155
280 77
205 279
61 158
61 259
268 61
2 8
275 144
250 61
40 21
293 131
20 119
85 200
90 61
46 109
153 61
21 61
61 69
203 258
238 280
268 61
49 27
61 221
265 74
198 61
141 73
231 209
182 52
61 5
31 220
239 61
143 25
131 61
140 218
66 295
258 194
84 200
141 150
127 61
171 260
61 44
61 22
26 244
61 279
114 61
61 81
100 61
297 61
19 69
263 20
113 40
76 61
131 249
99 13
61 153
134 259
52 240
92 166
283 61
232 156
61 91
6 61
90 243
61 208
51 223
252 61
121 206
126 293
228 189
60 78
93 61
167 141
13 61
239 100
13 5
61 178
243 54
61 274
286 61
288 64
61 36
276 84
114 239
230 244
70 291
105 61
61 102
61 288
207 164
181 222
119 27
234 188
82 272
217 76
78 104
215 293
123 202
61 202
168 288
137 159
55 61
292 30
98 151
93 199
227 24
94 61
61 214
151 61
173 290
39 61
153 146
38 96
19 61
4 156
110 61
216 61
61 176
108 73
100 117
61 157
154 283
128 61
201 252
89 242
61 20
77 227
42 276
61 67
130 201
42 61
61 80
61 189
110 126
214 177
61 222
169 229
102 145
70 41
69 197
61 82
162 273
28 93
61 174
218 61
32 8
61 9
84 254
257 23
121 51
61 224
40 61
71 139
61 193
61 275
144 19
61 198
214 133
12 198
80 10
81 135
154 61
47 85
72 237
39 35
199 167
230 107
119 204
61 50
109 217
16 114
61 55
279 224
61 10
61 187
181 148
164 205
202 3
191 46
125 178
219 213
122 75
271 248
256 61
295 207
289 271
139 297
61 54
236 61
61 26
61 210
60 61
105 8
245 61
161 90
269 10
61 184
61 99
297 61
76 124
61 232
225 259
61 50
226 61
61 296
232 118
61 187
129 152
61 238
249 292
119 274
61 95
170 101
44 62
260 210
79 263
61 107
33 79
95 53
138 107
224 61
15 61
61 257
211 61
181 145
61 126
148 61
61 79
261 145
158 105
11 244
294 247
282 154
61 48
149 16
61 193
61 158
13 61
5 219
61 11
66 156
44 83
252 43
72 163
55 251
146 61
102 61
61 139
290 122
223 22
123 61
61 190
201 61
61 214
187 203
95 203
36 61
7 162
137 61
207 61
197 18
61 235
130 165
283 42
224 60
61 115
61 261
00110011000000100010100010001100010110000110101010001100010110110110011000001111100111010000100011010001101111000000000111000111001100000001011101000111111111000101000011101010010111101011000001110000010100101110001011101001110010000011110000000101011000101101100100001100010110110000001011100011