\(\text{Solution}\)
高维莫队的一次尝试
最小众数似乎要求我们刻画能回滚的高维莫队
但这并不友好
修改有 \(O(n^{\frac 7 4})\)，询问只有 \(O(n)\)
考虑友好的分块，那么就加个值域分块
询问便可以先得到众数的出现次数，然后逐块枚举找到存在众数的块，再在块中枚举数判断是否为众数
发现只需维护块内数出现次数的最大值，每种出现次数有多少种数
于是时间复杂度 \(O(n^{\frac 7 4}+q\sqrt V)\)，空间 \(O(V\sqrt V)\)
可以通过，但：得手动调块长（艰难），卡点常
事实上有更优美的做法
上述方法把树拍到 \(dfs\) 序上缺失了与树相关的美感
注意到统计与子树相关通常会考虑树上启发式合并，但需要的是两棵子树
不妨类似点分树，把树上启发式合并加点删点的过程记下来，那么就是长为 \(O(n \log n)\) 的操作序列
此时一棵子树的信息变成了前缀操作序列，那么询问就可以当二维莫队跑了，同样套用值域分块
稍微修改一下莫队指针移动贡献的更新就好（因为是两段前缀，所以指针增大就加入当前操作，减小加入当前操作的逆操作）
时间复杂度 \(O(n\log n\sqrt n+q\sqrt V)\)，空间 \(O(n\log n+V\sqrt V)\)
下面代码放入高维莫队做法（暴力无脑）
\(\text{warning}:\) 有根树不代表边的读入有向，又一次瞪了一百年。。。
\(\text{Code}\)
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
template<typename Tp>
void read(Tp &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
const int N = 2e5 + 5;
int n, m, a[N], dfc, dfn[N], rev[N], sz[N], pos[N], ans[N];
vector<int> G[N];
void dfs(int u, int fa) {
dfn[u] = ++dfc, rev[dfc] = u, sz[u] = 1;
for(int v : G[u]) if (v ^ fa) dfs(v, u), sz[u] += sz[v];
}
struct Que{
int l1, r1, l2, r2, id;
bool operator < (Que b) {
if (pos[l1] ^ pos[b.l1]) return l1 < b.l1;
if (pos[r1] ^ pos[b.r1]) return r1 < b.r1;
if (pos[l2] ^ pos[b.l2]) return l2 < b.l2;
return ((pos[l1] ^ pos[r1] ^ pos[l2]) & 1) ? (r2 < b.r2) : (r2 > b.r2);
}
}Q[N];
struct SqrtD {
#define B 450
int pos[N], cnt[N], mx[B], tmp[B];
vector<int> sum[B];
void init() {
for(int i = 1; i <= N - 5; i++) pos[i] = (i - 1) / B + 1;
for(int i = 1; i <= n; i++) ++tmp[pos[a[i]]];
for(int i = 1; i <= pos[N - 5]; i++) sum[i].resize(tmp[i] * 2 + 2), sum[i][0] = 2e9;
}
void Add(int x) {
x = a[rev[x]], (cnt[x] > 0 && --sum[pos[x]][cnt[x]]);
++cnt[x], (cnt[x] > 0 && ++sum[pos[x]][cnt[x]]);
(sum[pos[x]][mx[pos[x]] + 1] && ++mx[pos[x]]);
}
void Del(int x) {
x = a[rev[x]], (cnt[x] > 0 && --sum[pos[x]][cnt[x]]);
--cnt[x], (cnt[x] > 0 && ++sum[pos[x]][cnt[x]]);
(!sum[pos[x]][mx[pos[x]]] && --mx[pos[x]]);
}
int Query() {
int Mx = 0;
for(int i = 1; i <= pos[N - 5]; i++) Mx = max(Mx, mx[i]);
for(int i = 1; i <= pos[N - 5]; i++) if (mx[i] == Mx)
for(int j = (i - 1) * B + 1; j <= i * B; j++) if (cnt[j] == Mx) return j;
}
}ds;
int main() {
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1, u, v; i < n; i++) read(u), read(v), G[u].eb(v), G[v].eb(u);
int bl = 6000;
for(int i = 1; i <= n; i++) pos[i] = (i - 1) / bl + 1;
dfs(1, 0), read(m);
for(int i = 1, x, y; i <= m; i++)
read(x), read(y), Q[i] = Que{dfn[x], dfn[x] + sz[x] - 1, dfn[y], dfn[y] + sz[y] - 1, i};
sort(Q + 1, Q + m + 1), ds.init();
for(int i = 1, l1 = 1, r1 = 0, l2 = 1, r2 = 0; i <= m; i++) {
while (l1 < Q[i].l1) ds.Del(l1++);
while (l1 > Q[i].l1) ds.Add(--l1);
while (r1 < Q[i].r1) ds.Add(++r1);
while (r1 > Q[i].r1) ds.Del(r1--);
while (l2 < Q[i].l2) ds.Del(l2++);
while (l2 > Q[i].l2) ds.Add(--l2);
while (r2 < Q[i].r2) ds.Add(++r2);
while (r2 > Q[i].r2) ds.Del(r2--);
ans[Q[i].id] = ds.Query();
}
for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}