P3603 Yukiteru

Time limit 3 s, memory limit 512 MB. In the third loop, Yuno was appointed as the kamisama, and she immediately rushed to the second loop to find Yukiteru. However, according to the setting, two parallel worlds cannot affect each other, which means in principle Yuno cannot go to the second world. At this moment Deus popped out again and said, actually the setting was the author lying to you; as long as the power of love is strong enough, anything can be done (what a melodrama). Deus: Yuno, will you do anything for Yukiteru? Yuno: Of course, that goes without saying. Deus: Then help me solve a problem. Yuno: As long as it’s not data structures, I’ll do any problem. Deus: The problem setter is that n???????? guy. Besides dumb data structures, what else does he write (copy)... Yuno: You have a point... Deus: Didn’t you insta-solve the last one in two minutes? This one is even easier. Yuno: (quietly) Actually that one was done by a big shot on bzoj. Deus: Fine, it’s happily decided then. 

Given a tree with n nodes. Each node has a weight. There are m queries. For each query, you are given multiple paths. Consider the union of these paths, and ask: - how many distinct node weights appear, and - the mex of those weights. The mex of a set is the smallest non-negative integer that does not appear; note that 0 counts. For example, if the set is 1, 9, 2, 6, 0, 8, 1, 7, then the distinct weights that appear are 0, 1, 2, 6, 7, 8, 9 (7 kinds). Since 3 does not appear, the mex is 3. 

- The first line contains three integers n and m as described above, and an integer f. - If f = 0, it means Deus did not use magic. - If f = 1, it means Deus used magic. - The second line contains n integers, the node weights. - The next n − 1 lines each contain two integers x and y, indicating there is an edge between nodes x and y. It is guaranteed to be a tree. - The next m lines each describe a query: - Each line starts with an integer a, the number of paths in this query. - Then follow 2a integers representing the a pairs (x1, y1) (x2, y2) ... corresponding to the paths. - If the testdata has been blessed by Deus’s magic (f = 1), then all these 2a integers must be xor-ed with the previous query’s answer lastans. For the first query, lastans = 0. Since each query has two answers, lastans is the sum of those two answers. - If there is no magic (f = 0), then −1 s and do not xor.

Output m lines. Each line contains two integers: the number of distinct node weights and the mex.

Let the sum of all a over all queries be q. Constraints: - For 20% of the testdata: n, q ≤ 1000, f = 0. - For an additional 30% of the testdata: n, q ≤ 100000, the tree is a path, f = 0. - For all testdata: n, q ≤ 100000, and node weights ≤ 30000. Finally, Yuno wishes everyone a Happy New Year.  Translated by ChatGPT 5