P15534 【MYCOI R1】The Market of Cats

Cat City has $n$ markets, connected by $n-1$ bidirectional roads such that any two markets can reach each other via some paths. Each market sells two types of goods $a_u, b_u$ ($a_u \neq b_u$). Now Xiao Meng, a cat, has planned $Q$ journeys. Each time, Xiao Meng will start from market $u$ and travel along the **shortest path** to market $v$. When passing through a market (including $u$ and $v$), Xiao Meng will attempt to trade. If Xiao Meng already possesses one of the goods sold at that market, he will exchange it for the other good sold there; otherwise, he keeps his original goods. Initially, Xiao Meng possesses a good of type $x$. Find out what type of good Xiao Meng ends up with after the journey.

The first line contains two positive integers $n, Q$. The next two lines each contain $n$ positive integers. The $i$-th number in the first line is $a_i$, and the $i$-th number in the second line is $b_i$. The following $n-1$ lines each contain two positive integers $u, v$, indicating a road between market $u$ and market $v$. The following $Q$ lines each contain three positive integers $u, v, x$, describing a journey.

Output $Q$ lines, each containing a positive integer representing the type of good Xiao Meng finally possesses.

**This problem uses bundled testing.** ::cute-table{tuack} | Subtask | Constraints | Special Properties | Points | |:---------:|:---------------:|:----------------------:|:-----:| | Subtask 1 | $N,Q \leq 1000$ | The tree is a chain | 5 | | Subtask 2 | $N,Q \leq 1000$ | None | 15 | | Subtask 3 | $N,Q \leq 10^6$ | $\forall i, a_i=1, b_i=2$ | 10 | | Subtask 4 | $N,Q \leq 10^6$ | The tree is a chain | 15 | | Subtask 5 | $N,Q \leq 10^5$ | None | 25 | | Subtask 6 | $N,Q \leq 10^6$ | None | 30 | For $100\%$ of the data, $2 \le N \le 10^6$, $1 \le Q \le 10^6$, $1 \le a_i, b_i \le N$. **Please pay special attention to the time and memory limits.** #### Explanation of Example 1  As shown in the figure, for the first query: starting from market $3$, because Xiao Meng possesses good $1$, he exchanges it for $5$. At market $2$, there is no matching good, so no exchange occurs. At market $4$, he exchanges it for good $2$. ### A Fast I/O Template Is Provided ```cpp namespace io { char *p1,*p2,buf[100001]; #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) template inline typename __gnu_cxx::__enable_if::__type read() { T sum=0; char ch; do ch=getchar(); while(!isdigit(ch)); do sum=(sum