P14655 Same Moon Return

Little L gave you a tree with $n-1$ edges. The $i$-th edge is $(u_i, v_i)$. Some edges already have fixed directions. Little L wants you to determine the direction of every remaining edge so that the following conditions are satisfied: - For each node $i$, let $k_i$ be the number of incoming edges of node $i$. Then $W_{i,k_i}=1$, where $W_{i,j}$ is an input array with values in $\{0,1\}$. - Let the $01$ sequence $s_i$ be defined as follows: if the $i$-th edge is directed from $u_i$ to $v_i$, then $s_i=0$; otherwise $s_i=1$. Based on this, output the lexicographically smallest sequence $s_i$. If no solution exists, output $-1$. Otherwise, output one line representing the lexicographically smallest $s_i$.

The first line contains an integer $T$, the number of test cases. For each test case, the first line contains an integer $n$. Then follow $n-1$ lines, each containing two integers $u_i, v_i$. Then follow $n$ lines, each being a $01$ string of length $d_i+1$, representing $W_{i,0}\to W_{i,d_i}$, where $d_i$ is the degree of node $i$. Then follows one string of length $n-1$ consisting of `0`, `1`, and `?`. Here `0` and `1` mean the corresponding edge direction is already fixed, and `?` means it is not fixed.

If there is no solution, output `-1`. Otherwise, output one line: a $01$ string of length $n-1$ representing $s$.

For $20\%$ of the testdata, $T\leq 20$ and $n\leq 16$. For $40\%$ of the testdata, $\sum n\leq 100$. For $60\%$ of the testdata, $\sum n\leq 2000$. For the other $20\%$ of the testdata, the input string contains only `?`. For $100\%$ of the testdata, $2\leq \sum n\leq 5\times 10^5$ and $n\geq 2$. Translated by ChatGPT 5