传送门

第一眼看貌似可以树剖，然而那个绝对值不知怎么维护

求最小连通块我只会\(k^2\)

主席树貌似可以用来查询区间内与某个数差的绝对值的最小值？

确实，每次查大于等于该数的最小数和小于等于该数的最大数即可

至于具体实现，实际上可以转化为求一个区间内最左/右边的数

很容易写出一个线段树上\(O(nlogn)\)的暴力遍历

但这里用的只要求第一个，可以按顺序找，找到第一个就跳出，单次复杂度\(O(logn)\)

至于查询区间和log划分区间间的问题，到了一个节点，如果它已经不在查询区间中，返回一个标记值即可

至于求连通块的问题：

• 一棵树上，给定n个点，求这n个点所在的最小连通块中的最值之类的东西

  其实找到它们的lca，\(O(k)\)遍历一次，每次查询一个点与lca之间的路径即可

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#define int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
inline int read() {
    int ans=0, f=1; char c=getchar();
    while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
    while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
    return ans*f;
}

int n, q, typ;
int head[N], size, a[N], x[N];
struct edge{int to, next;}e[N<<1];
inline void add(int s, int t) {edge* k=&e[++size]; k->to=t; k->next=head[s]; head[s]=size;}
//struct que{int r, k; vector<int> v;}que[N];

namespace force{
    bool vis[N];
    int dfs(int u, int to, int r, int fa) {
        if (u==to) return abs(a[u]-r);
        for (int i=head[u],v,t; i; i=e[i].next) {
            v = e[i].to;
            if (v!=fa) {
                t=dfs(v, to, r, u);
                if (t!=-1) return min(t, abs(a[u]-r));
            }
        }
        return -1;
    }
    void solve() {
        for (int i=1,r,k,ans; i<=q; ++i) {
            ans=INF;
            r=read(); k=read();
            //cout<<r<<' '<<k<<endl;
            for (int j=1; j<=k; ++j) x[j]=read();
            for (int j=1; j<=k; ++j)
                for (int h=j; h<=k; ++h)
                    ans=min(ans, dfs(x[j], x[h], r, 0));
            printf("%d\n", ans);
        }
        exit(0);
    }
}

namespace force2{
    bool vis[N];
    int rot;
    int dfs(int u, int r, int fa) {
        int ans=INF;
        if (vis[u]) ans=min(ans, abs(a[u]-r));
        for (int i=head[u],v,t; i; i=e[i].next) {
            v = e[i].to;
            if (v!=fa) {
                t=dfs(v, r, u);
                if (t!=-1) ans=min(ans, min(t, abs(a[u]-r)));
                if (!ans) return 0;
            }
        }
        return ans==INF?-1:ans;
    }
    void solve() {
        for (int i=1,r,k,ans; i<=q; ++i) {
            ans=INF;
            r=read(); k=read();
            //cout<<r<<' '<<k<<endl;
            for (int j=1; j<=k; ++j) x[j]=read(), vis[x[j]]=1;
            printf("%d\n", dfs(x[1], r, 0));
            for (int j=1; j<=k; ++j) vis[x[j]]=0;
        }
        exit(0);
    }
}

namespace task{
    int dep[N], siz[N], msiz[N], mson[N], top[N], id[N], rk[N], fa[N], tot;
    int rot[N], tot2, r[N*3], k[N*3], uni[N<<3], usize, lst;
    vector<ll> x[N*3];
    struct pst{
        int tl, tr, cnt, lson, rson;
        #define t(p) tree[p]
        #define tl(p) tree[p].tl
        #define tr(p) tree[p].tr
        #define cnt(p) tree[p].cnt
        #define l(p) tree[p].lson
        #define r(p) tree[p].rson
        #define pushup(p) cnt(p)=cnt(l(p))+cnt(r(p))
    }tree[N*80];
    int upd(int p1, int p2, int l, int r, int pos) {
        p1=++tot2; t(p1)=t(p2); tl(p1)=l; tr(p1)=r;
        if (l>=r) {cnt(p1)=cnt(p2)+1; return p1;}
        int mid=(l+r)>>1;
        if (pos<=mid) l(p1)=upd(l(p1), l(p2), l, mid, pos);
        else r(p1)=upd(r(p1), r(p2), mid+1, r, pos);
        pushup(p1);
        return p1;
    }
    int qleft(int p1, int p2, int l, int r) {
        //cout<<"qleft "<<p1<<' '<<p2<<' '<<l<<' '<<r<<endl;
        if (l>tr(p2) || r<tl(p2)) return 0;
        if (tl(p2)==tr(p2)) {/*cout<<"return "<<cnt(p2)-cnt(p1)<<' '<<tl(p2)<<endl;*/ return (cnt(p2)-cnt(p1))?tl(p2):0;}
        int mid=(tl(p2)+tr(p2))>>1, ans=INF, t;
        if (l<=mid && cnt(l(p2))-cnt(l(p1))) {t=qleft(l(p1), l(p2), l, r); ans=min(ans, !t?INF:t);}
        if (ans!=INF) return ans;
        if (r>mid && cnt(r(p2))-cnt(r(p1))) {t=qleft(r(p1), r(p2), l, r); ans=min(ans, !t?INF:t);}
        //puts("error");
        return ans==INF?0:ans;
    }
    int qright(int p1, int p2, int l, int r) {
        //cout<<"qright: "<<p1<<' '<<p2<<' '<<l<<' '<<r<<endl;
        if (l>tr(p2) || r<tl(p2)) return 0;
        if (tl(p2)==tr(p2)) {/*cout<<"return "<<cnt(p2)-cnt(p1)<<' '<<tl(p2)<<endl;*/ return (cnt(p2)-cnt(p1))?tl(p2):0;}
        int mid=(tl(p2)+tr(p2))>>1, ans=0, t;
        if (r>mid && cnt(r(p2))-cnt(r(p1))) {t=qright(r(p1), r(p2), l, r); ans=max(ans, t);}
        if (ans) return ans;
        if (l<=mid && cnt(l(p2))-cnt(l(p1))) {t=qright(l(p1), l(p2), l, r); ans=max(ans, t);}
        //puts("error");
        return ans;
    }
    void dfs1(int u, int pa) {
        siz[u]=1;
        for (int i=head[u],v; i; i=e[i].next) {
            v = e[i].to;
            if (v==pa) continue;
            dep[v]=dep[u]+1; fa[v]=u;
            dfs1(v, u);
            siz[u]+=siz[v];
            if (siz[v]>msiz[u]) msiz[u]=siz[v], mson[u]=v;
        }
    }
    void dfs2(int u, int f, int t) {
        top[u]=t;
        id[u]=++tot;
        rot[tot]=upd(rot[tot], rot[tot-1], 1, usize, lower_bound(uni+1, uni+usize+1, a[u])-uni);
        //cout<<"upd: "<<tot<<' '<<u<<' '<<lower_bound(uni+1, uni+usize+1, a[u])-uni<<' '<<uni[lower_bound(uni+1, uni+usize+1, a[u])-uni]<<endl;
        rk[tot]=u;
        if (!mson[u]) return ;
        dfs2(mson[u], u, t);
        for (int i=head[u],v; i; i=e[i].next) {
            v = e[i].to;
            if (v!=f && v!=mson[u]) dfs2(v, u, v);
        }
    }
    int query(int a, int b, int r) {
        //cout<<"query "<<a<<' '<<b<<' '<<r<<endl;
        int ans=INF, q1, q2;
        int rb=lower_bound(uni+1, uni+usize+1, r)-uni;
        //cout<<"rb: "<<rb<<endl;
        while (top[a]!=top[b]) {
            if (dep[top[a]]<dep[top[b]]) swap(a, b);
            //cout<<"qid: "<<id[top[a]]<<' '<<id[a]<<endl;
            q1=qleft(rot[id[top[a]]-1], rot[id[a]], rb, usize), q2=qright(rot[id[top[a]]-1], rot[id[a]], 1, rb);
            //cout<<"q1q2: "<<q1<<' '<<q2<<endl;
            ans=min(ans, min(q1?(uni[q1]-r):INF, q2?(r-uni[q2]):INF));
            if (!ans) return 0;
            a = fa[top[a]];
        }
        if (dep[a]>dep[b]) swap(a, b);
        //cout<<"qid: "<<id[a]<<' '<<id[b]<<endl;
        q1=qleft(rot[id[a]-1], rot[id[b]], rb, usize), q2=qright(rot[id[a]-1], rot[id[b]], 1, rb);
        //cout<<"q1q2: "<<q1<<' '<<q2<<endl;
        ans=min(ans, min(q1?(uni[q1]-r):INF, q2?(r-uni[q2]):INF));
        return ans;
    }
    int lca(int a, int b) {
        while (top[a]!=top[b]) {
            if (dep[top[a]]<dep[top[b]]) swap(a, b);
            a = fa[top[a]];
        }
        if (dep[a]>dep[b]) swap(a, b);
        return a;
    }
    void init() {
        dep[1]=1;
        dfs1(1, 0);
        dfs2(1, 0, 1);
    }
    void solve() {
        for (int i=1; i<=q; ++i) {
            r[i]=read(); k[i]=read(); uni[++usize]=r[i];
            for (int j=1,t; j<=k[i]; ++j) {t=read(); x[i].push_back(t);}
        }
        for (int i=1; i<=n; ++i) uni[++usize]=a[i];
        //cout<<"usize: "<<usize<<endl;
        //cout<<"uni: "; for (int i=1; i<=usize; ++i) cout<<uni[i]<<' '; cout<<endl;
        sort(uni+1, uni+usize+1);
        usize=unique(uni+1, uni+usize+1)-uni-1;
        //cout<<"usize: "<<usize<<endl;
        //cout<<"uni: "; for (int i=1; i<=usize; ++i) cout<<uni[i]<<' '; cout<<endl;
        init();
        for (int i=1,anc,ans; i<=q; ++i) {
            anc=(x[i][0]-1+lst*typ)%n+1, ans=INF;
            for (int j=1; j<k[i]&&anc!=1; ++j) anc=lca(anc, (x[i][j]-1+lst*typ)%n+1);
            //cout<<"anc: "<<anc<<endl;
            for (int j=0; j<k[i]&&ans; ++j) ans=min(ans, query((x[i][j]-1+lst*typ)%n+1, anc, r[i])); //, cout<<"nowans: "<<ans<<endl;
            printf("%d\n", ans);
            lst=ans;
        }
        //cout<<qleft(rot[0], rot[3], 1, 5)<<endl;
        //cout<<qright(rot[1], rot[3], 1, 3)<<endl;
    }
}

signed main()
{
    #ifdef DEBUG
    freopen("1.in", "r", stdin);
    #endif
    bool same=1, less1=1, ris1=1, chain=1;

    n=read(); q=read(); typ=read();
    if (!q) return 0;
    for (int i=1; i<=n; ++i) {
        a[i]=read();
        if (i!=1 && a[i]!=a[i-1]) same=0;
    }
    for (int i=1,u,v; i<n; ++i) {
        u=read(); v=read();
        add(u, v); add(v, u);
        if (v!=u+1) chain=0;
    }
    task::solve();
    #if 0
    if (n<=1000) force2::solve();
    for (int i=1,r,k; i<=q; ++i) {
        r=read(); k=read();
        for (int j=1; j<=k; ++j) x[j]=read(), force2::vis[x[j]]=1;
        if (!k) continue;
        else if (k==1 || same) printf("%d\n", abs(a[x[1]]-r));
        else printf("%d\n", force2::dfs(x[1], r, 0));
        for (int j=1; j<=k; ++j) force2::vis[x[j]]=0;
        //else if (r==1) printf("%d\n", task2::qmin(1,
    }
    #endif

    return 0;
}