线段树能换成ST表，而且ST更快。求区间mex转换为求除了这段的数的最小值。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
#define debug(x) cerr<<#x<<":"<<x<<"\n";
#define debugv(v) cerr<<#v<<":\n";for(int i=0;i<v.size();i++) cerr<<v[i]<<" ";cerr<<"\n";
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
const int N=2e5+10;
int a[N],b[N],sz[N],deep[N],f[N],son[N],t[N],mp[N];
int dp[N][32];
vector<int> adj[N];
struct node{
    int l,r,mn;
}seg[N<<2];
const int INF=1e9;
void pushup(int p){
    seg[p].mn=min(seg[ls(p)].mn,seg[rs(p)].mn);
}
void build(int p,int l,int r){
    seg[p]={l,r,INF};
    if(l==r){
        seg[p].mn=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
int query_range(int l,int r,int p){
    if(l<=seg[p].l&&seg[p].r<=r){
        return seg[p].mn;
    }
    int res=INF;
    int mid=(seg[p].l+seg[p].r)>>1;
    if(l<=mid) res=min(res,query_range(l,r,ls(p)));
    if(mid<r) res=min(res,query_range(l,r,rs(p)));
    return res;
}

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto dfs1=[&](auto&& self,int u,int fa)->void {
        sz[u]=1,deep[u]=deep[fa]+1,f[u]=fa;
        for(auto v:adj[u]){
            if(v==fa) continue;
            self(self,v,u);
            if(sz[son[u]]<sz[v]) son[u]=v;
            sz[u]+=sz[v];
        }
    };
    int cnt=0;
    auto dfs2=[&](auto&& self,int u,int tmp)->void {
        t[u]=tmp;
        mp[u]=++cnt;
        b[cnt]=a[u];
        if(!son[u]) return;
        self(self,son[u],tmp);
        for(auto v:adj[u]){
            if(v==f[u]||v==son[u]) continue;
            self(self,v,v);
        }
    };
    dfs1(dfs1,1,0);
    dfs2(dfs2,1,1);
    build(1,1,n);
    // for(int i=1;i<=n;i++){
    //     dp[i][0]=b[i];
    // }
    // int p=log2(n);
    // for(int k=1;k<=p;k++){
    //     for(int s=1;s+(1<<k)-1<=n;s++){
    //         dp[s][k]=min(dp[s][k-1],dp[s+(1<<(k-1))][k-1]);
    //     }
    // }
    // auto query_range=[&](int l,int r)->int {
    //     int k=log2(r-l+1);
    //     return min(dp[l][k],dp[r-(1<<k)+1][k]);
    // };
    auto query=[&](int l,int r)->int {
        vector<int> v;
        while(t[l]!=t[r]){
            if(deep[t[l]]<deep[t[r]]) swap(l,r);
            v.push_back(mp[t[l]]);
            v.push_back(mp[l]);
            l=f[t[l]];
        }
        if(deep[l]<deep[r]) swap(l,r);
        v.push_back(mp[r]);
        v.push_back(mp[l]);
        sort(v.begin(),v.end());
        int mn=1;
        int res=n;
        for(int i=0;i<v.size();i+=2){
            int pos=v[i]-1;
            if(mn<=pos) res=min(res,query_range(mn,pos,1));
            mn=v[i+1]+1;
        }
        if(mn<=n) res=min(res,query_range(mn,n,1));
        return res;
    };
    while(m--){
        int l,r;cin>>l>>r;
        int ans=query(l,r);
        cout<<ans<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}