P10388 [Lqiao Cup 2024 NOI Qualifier A] Team Building

Xiaolan is doing team building with friends. There is a game that requires two people to cooperate. Each person receives a tree of size $n$ and $m$ respectively, and each node on the tree has a positive integer weight. Starting from the root node $1$ of their own tree, each person needs to walk to some leaf node. The weights of all nodes on the path from the root to that leaf form a positive integer sequence. Their score is the length of the longest common prefix of the two sequences. Given the two trees, compute the maximum possible score.

The first line contains two positive integers $n, m$, separated by a space. The second line contains $n$ positive integers $c_1, c_2,\cdots , c_n$, separated by spaces, where $c_i$ denotes the weight of node $i$ in the first tree. The third line contains $m$ positive integers $d_1, d_2,\cdots, d_m$, separated by spaces, where $d_i$ denotes the weight of node $i$ in the second tree. The next $n - 1$ lines each contain two positive integers $u_i , v_i$ indicating that the first tree has an edge between $u_i$ and $v_i$. The next $m - 1$ lines each contain two positive integers $p_i , q_i$ indicating that the second tree has an edge between $p_i$ and $q_i$.

Output one line containing one integer, the answer.

For $20\%$ of the test cases, $1 \le n, m \le 500$. For all test cases, $1 \le n, m \le 2 \times 10^5$, $1 \le c_i , d_i \le 10^8$, $1 \le u_i , v_i \le n$, $1 \le p_i , q_i \le m$. For any node, the weights of its child nodes are all distinct. Translated by ChatGPT 5