P5406 [THUPC 2019] Find a Tree

Define $\otimes_1, \otimes_2, \otimes_3$ as bitwise AND, bitwise OR, and bitwise XOR, respectively. Let $a_i$ denote the $i$-th binary bit of $a$ from low to high. Define a new operation $\oplus$ on $w$-bit binary numbers such that for each bit $(a\oplus b)_i$ of the result $a\oplus b$, we have $(a\oplus b)_i = a_i \otimes_{o_i} b_i$. It is not hard to verify that the operation $\oplus$ is associative and commutative. Given an undirected graph with $n$ vertices and $m$ edges, each edge weight is a $w$-bit binary number (i.e., a non-negative integer less than $2^w$). Please find a spanning tree of the original graph. Suppose the edge weights in your spanning tree are $v_1,\cdots,v_{n-1}$. Please maximize $v_1\oplus v_2\oplus\cdots\oplus v_{n-1}$.

The first line contains two positive integers $n,m$. The second line contains a string of length $w$. Each character in the string is one of `&`, `|`, `^` (representing AND, OR, XOR, respectively), indicating each $\otimes_{o_i}$. The next $m$ lines each contain three non-negative integers $x,y,v$, representing an edge connecting $x$ and $y$ with weight $v$. It is guaranteed that $1\leq x,y\leq n$, $0\le v < 2^w$. For all testdata, $1\le n\le 70,1\le m\le 5000,1\le w \le 12$.

Output one line with one number, indicating the answer. If the graph is disconnected, output `-1`.

### About the testdata For some reasons, the testdata only keeps the last $20$ vertices. ### Copyright information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019. Resources such as solutions can be found at . Translated by ChatGPT 5