Two Subtrees

题意翻译

给你一棵有根树，每次给出两个子树（可能有交），求这两个子树中所有的点权的最小众数。如果一个点被两个子树覆盖算两次。

题目描述

You are given a rooted tree consisting of $ n $ vertices. The vertex $ 1 $ is the root. Each vertex has an integer written on it; this integer is $ val_i $ for the vertex $ i $ . You are given $ q $ queries to the tree. The $ i $ -th query is represented by two vertices, $ u_i $ and $ v_i $ . To answer the query, consider all vertices $ w $ that lie in the subtree of $ u_i $ or $ v_i $ (if a vertex is in both subtrees, it is counted twice). For all vertices in these two subtrees, list all integers written on them, and find the integer with the maximum number of occurrences. If there are multiple integers with maximum number of occurrences, the minimum among them is the answer.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree. The second line contains $ n $ integers $ val_1, val_2, \dots, val_n $ ( $ 1 \le val_i \le 2 \cdot 10^5 $ ) — the numbers written on the vertices. Then $ n - 1 $ lines follow, each containing two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ ) representing an edge between vertices $ x $ and $ y $ . These edges form a tree. The next line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of queries to process. Then $ q $ lines follow. The $ i $ -th of them containing two numbers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ ) — the roots of subtrees in the $ i $ -th query.

输出格式

For each query, print one integer — the number that has the maximum amount of occurrences in the corresponding pair of subtrees (if there are multiple such numbers, print the minimum one among them).

输入输出样例

输入样例 #1

8
2 1 3 2 3 3 2 4
1 2
1 3
2 4
3 5
3 6
3 7
7 8
6
2 7
3 7
2 3
1 1
5 6
1 3

输出样例 #1

2
3
3
2
3
3

说明

In the $ 1 $ -st query, the pair of subtrees consists of vertices $ [2, 4, 7, 8] $ , and the numbers written on them are $ \{1, 2, 2, 4\} $ . The number $ 2 $ occurs twice, all other numbers — at most once, so the answer is $ 2 $ . In the $ 2 $ -nd query, the pair of subtrees consists of vertices $ [3, 5, 6, 7, 7, 8, 8] $ , and the numbers written on them are $ \{3, 3, 3, 2, 2, 4, 4\} $ . The number $ 3 $ has the maximum number of occurrences. In the $ 4 $ -th query, the pair of subtrees consists of vertices $ [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8] $ , and the numbers written on them are $ \{2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4\} $ . The numbers $ 2 $ and $ 3 $ are the most common, the minimum of them is $ 2 $ .

**题目大意：**

题目给出了一棵有根树，树上的每个节点都有一个整数值。问题要求对于每次给定的两个子树，找出这两个子树中所有节点值出现次数最多的最小值。如果一个节点同时被两个子树覆盖，那么它的值会被计算两次。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 \( n \) (\( 1 \le n \le 2 \cdot 10^5 \))，表示树中节点的数量。
- 第二行包含 \( n \) 个整数 \( val_1, val_2, \dots, val_n \) (\( 1 \le val_i \le 2 \cdot 10^5 \))，表示每个节点的值。
- 接下来的 \( n - 1 \) 行，每行包含两个整数 \( x \) 和 \( y \) (\( 1 \le x, y \le n \))，表示节点 \( x \) 和节点 \( y \) 之间的一条边。这些边构成了一棵树。
- 下一行包含一个整数 \( q \) (\( 1 \le q \le 2 \cdot 10^5 \))，表示要处理的查询数量。
- 然后是 \( q \) 行，每行包含两个数字 \( u_i \) 和 \( v_i \) (\( 1 \le u_i, v_i \le n \))，表示第 \( i \) 个查询中的两个子树的根节点。

**输出格式：**
- 对于每个查询，输出一行，包含一个整数，表示在对应的两个子树中出现次数最多的节点值（如果有多个这样的值，则输出最小的那个）。**题目大意：** 题目给出了一棵有根树，树上的每个节点都有一个整数值。问题要求对于每次给定的两个子树，找出这两个子树中所有节点值出现次数最多的最小值。如果一个节点同时被两个子树覆盖，那么它的值会被计算两次。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 \( n \) (\( 1 \le n \le 2 \cdot 10^5 \))，表示树中节点的数量。 - 第二行包含 \( n \) 个整数 \( val_1, val_2, \dots, val_n \) (\( 1 \le val_i \le 2 \cdot 10^5 \))，表示每个节点的值。 - 接下来的 \( n - 1 \) 行，每行包含两个整数 \( x \) 和 \( y \) (\( 1 \le x, y \le n \))，表示节点 \( x \) 和节点 \( y \) 之间的一条边。这些边构成了一棵树。 - 下一行包含一个整数 \( q \) (\( 1 \le q \le 2 \cdot 10^5 \))，表示要处理的查询数量。 - 然后是 \( q \) 行，每行包含两个数字 \( u_i \) 和 \( v_i \) (\( 1 \le u_i, v_i \le n \))，表示第 \( i \) 个查询中的两个子树的根节点。 **输出格式：** - 对于每个查询，输出一行，包含一个整数，表示在对应的两个子树中出现次数最多的节点值（如果有多个这样的值，则输出最小的那个）。