P10787 [NOI2024] Tree Edge Orientation

Due to performance differences among judging machines, the original time limit was $3\ \mathrm{s}$, while on Luogu the time limit is $6\ \mathrm{s}$.

Given a tree with $n$ vertices, numbered from $1$ to $n$. The $i$-th edge $(1\leq i\leq n-1)$ connects vertices $u_i$ and $v_i$. Now we want to assign a direction to every edge of the tree. Any orientation can be described by a string $S=s_1s_2\ldots s_{n-1}$ of length $n-1$. Here, $s_i=0$ means the $i$-th edge is directed as $u_i \to v_i$; otherwise, $s_i=1$ means the $i$-th edge is directed as $v_i \to u_i$. Given $m$ pairs of vertices $(a_i,b_i)$, where $1\leq a_i,b_i \leq n$ and $a_i\neq b_i$. A **perfect orientation** is defined as follows: under this orientation, for every $1\leq i\leq m$, $a_i$ **cannot reach** $b_i$. Among all perfect orientations, find the one whose corresponding string is lexicographically smallest. **It is guaranteed that at least one perfect orientation exists**. We say the lexicographical order of $S=s_1s_2\ldots s_{n-1}$ is smaller than $T=t_1t_2\ldots t_{n-1}$ if there exists an index $k$ such that $s_1=t_1, s_2=t_2, \ldots, s_{k-1}=t_{k-1}$ and $s_k < t_k$.

The first line contains three non-negative integers $c,n,m$, representing the test point ID, the number of vertices in the tree, and the number of vertex pairs. Here $c=0$ means this test point is a sample. The next $n-1$ lines each contain two positive integers $u_i,v_i$, describing an edge of the tree. It is guaranteed that $1\leq u_i,v_i\leq n$ and these $n-1$ edges form a tree. The next $m$ lines each contain two positive integers $a_i,b_i$. It is guaranteed that $1\leq a_i,b_i \leq n$ and $a_i\neq b_i$.

Output one line containing a string $S=s_1s_2\ldots s_{n-1}$, the $01$ string corresponding to the lexicographically smallest perfect orientation.

**[Sample 1 Explanation]** In this sample, if $S=000$, then in this orientation $1$ can reach $4$ (there is a path $1\to 2\to 3\to 4$), so it is not a perfect orientation. If $S=001$, then in this orientation $3$ cannot reach $2$, and $1$ cannot reach $4$, so it is a perfect orientation. Therefore the answer is $001$. **[Sample 2 Explanation]** In this sample, any perfect orientation must satisfy that $4$ cannot reach $3$, and $5$ cannot reach $1$. Therefore $s_1=s_5=1$. If $s_2=s_3=0$, then there exists a path $1\to 2\to 3\to 4$, so $1$ can reach $4$. Hence it is not a perfect orientation. Therefore, all perfect orientations must have $S$ lexicographically not smaller than $10101$. It is also easy to verify that when $S=10101$, the corresponding orientation is a perfect orientation. **[Constraints]** For all testdata, it is guaranteed that $2\leq n\leq 5\times 10^5$, $1\leq m\leq 5\times 10^5$, $1\leq u_i,v_i\leq n$, and all edges form a tree; $1\leq a_i,b_i \leq n$ and $a_i\neq b_i$. It is guaranteed that at least one perfect orientation exists. ::cute-table{tuack} | Test point ID | $n$ | $m$ | Special property | | :----------: | :----------: | :----------: | :----------: | | $1\sim 3$ | $\leq 15$ | $\leq 50$ | None | | $4\sim 6$ | $\leq 300$ | $\leq 300$ | None | | $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$ | None | | $15,16$ | $\leq 10^5$ | $\leq 10^5$ | B | | $17,18$ | $\leq 10^5$ | $\leq 10^5$ | None | | $19\sim 21$ | $\leq 2\times 10^5$ | $\leq 2\times 10^5$ | None | | $22\sim 25$ | $\leq 5\times 10^5$ | $\leq 5\times 10^5$ | None | - Special property A: It is guaranteed that $(a,b)$ appears in $(a_i,b_i)$ if and only if $a\neq b$ and $a,b$ are not adjacent in the tree. - Special property B: It is guaranteed that the vertex numbered $1$ is adjacent to every other vertex in the tree. Translated by ChatGPT 5