对于这个 \(abs\) 就是求大于 \(r\) 的最小值,小于 \(r\) 的最大值,建权值线段树或平衡树。
因为是 \(k\) 个点的联通块,就是求它们的 \(lca\) 到它们的链,可持久化线段树就行
在这里,只需要儿子继承父亲即可,因为要求一条链。
在搜前趋时,右儿子有就搜右儿子,搜出一个答案后就停止,这样可以做到每次最多搜 \(log\) 个区间,只有一个区间会继续向下搜,所以总的也是 \(log\)
总复杂度 \(\mathcal O\rm (klogn)\)
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=1e5+7;
int first[N],st[N<<1][19],lg[N<<1],head[N],f[N],dep[N],a[N],p[N],lca,ol,t=1,typ,n,q,fg,mx,ans,lst;
struct edge{int v,nxt;}e[N<<1];
inline void add(int u,int v) {
e[t].v=v,e[t].nxt=first[u],first[u]=t++;
e[t].v=u,e[t].nxt=first[v],first[v]=t++;
}
void dfs_init(int x,int fa) {
f[x]=fa;
head[st[p(ol)][0]=x]=ol;
for (ri i(first[x]),v;i;i=e[i].nxt) {
if ((v=e[i].v)==fa) continue;
dep[v]=dep[x]+1;
dfs_init(v,x);
st[p(ol)][0]=x;
}
}
inline void init_rmq() {
dfs_init(1,0);
for (ri i(2);i<=ol;p(i)) lg[i]=lg[i>>1]+1;
ri k=lg[ol];
for (ri j(1);j<=k;p(j)) {
ri len=1<<j;
for (ri i(1);i+len-1<=ol;p(i)) {
ri x1=st[i][j-1],x2=st[i+(1<<j-1)][j-1];
st[i][j]=dep[x1]<dep[x2]?x1:x2;
}
}
}
inline int Getlca(int u,int v) {
if (head[u]>head[v]) swap(u,v);
int k=lg[head[v]-head[u]+1];
ri x1=st[head[u]][k],x2=st[head[v]-(1<<k)+1][k];
return dep[x1]<dep[x2]?x1:x2;
}
struct Seg{
#define ls(x) T[x].l
#define rs(x) T[x].r
#define up(x) T[x].nm=T[ls(x)].nm+T[rs(x)].nm
struct segmenttree{int l,r,nm;}T[N<<5];
int rt[N],tot;
void update(int &x,int p,int l,int r) {
if (!x) x=p(tot);
if (l==r) return (void)(p(T[x].nm));
int mid(l+r>>1);
if (p<=mid) update(ls(x),p,l,mid);
else update(rs(x),p,mid+1,r);
up(x);
}
int merge(int x,int y) {
if (!x||!y) return (x|y);
T[x].nm+=T[y].nm;
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
return x;
}
int calcx(int x,int pre,int l,int r) {
if (l==r) return l;
int mid(l+r>>1);
if (T[rs(x)].nm-T[rs(pre)].nm) return calcx(rs(x),rs(pre),mid+1,r);
return calcx(ls(x),ls(pre),l,mid);
}
int calcn(int x,int pre,int l,int r) {
if (l==r) return l;
int mid(l+r>>1);
if (T[ls(x)].nm-T[ls(pre)].nm) return calcn(ls(x),ls(pre),l,mid);
return calcn(rs(x),rs(pre),mid+1,r);
}
int queryx(int x,int pre,int l,int r,int lt,int rt) {
if (!x) return -1;
if (!(T[x].nm-T[pre].nm)) return -1;
if (l<=lt&&rt<=r) return calcx(x,pre,lt,rt);
int mid(lt+rt>>1),res(-1);
if (r>mid&&T[rs(x)].nm-T[rs(pre)].nm) res=queryx(rs(x),rs(pre),l,r,mid+1,rt);
if (res!=-1) return res;
if (l<=mid&&T[ls(x)].nm-T[ls(pre)].nm) res=queryx(ls(x),ls(pre),l,r,lt,mid);
return res;
}
int queryn(int x,int pre,int l,int r,int lt,int rt) {
if (!x) return -1;
if (!(T[x].nm-T[pre].nm)) return -1;
if (l<=lt&&rt<=r) return calcn(x,pre,lt,rt);
int mid(lt+rt>>1),res(-1);
if (l<=mid&&T[ls(x)].nm-T[ls(pre)].nm) res=queryn(ls(x),ls(pre),l,r,lt,mid);
if (res!=-1) return res;
if (r>mid&&T[rs(x)].nm-T[rs(pre)].nm) res=queryn(rs(x),rs(pre),l,r,mid+1,rt);
return res;
}
}T;
void dfs(int x) {
T.update(T.rt[x],a[x],1,mx);
if (f[x]) T.merge(T.rt[x],T.rt[f[x]]);
for (ri i(first[x]),v;i;i=e[i].nxt) {
if ((v=e[i].v)==f[x]) continue;
dfs(v);
}
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(q),read(typ);
for (ri i(1);i<=n;p(i)) read(a[i]),mx=cmax(mx,a[i]);
for (ri i(1),u,v;i<n;p(i)) read(u),read(v),add(u,v);
init_rmq();
dfs(1);
for (ri i(1),r,k;i<=q;p(i)) {
read(r),read(k);
ans=INT_MAX;
for (ri j(1);j<=k;p(j)) read(p[j]),p[j]=(p[j]-1+lst*typ)%n+1;
lca=p[1];
for (ri j(2);j<=k;p(j)) lca=Getlca(p[j],lca);
for (ri j(1);j<=k;p(j)) {
fg=0;
ri a1=T.queryx(T.rt[p[j]],T.rt[f[lca]],1,r,1,mx),a2=-1;
if (r<=mx) a2=T.queryn(T.rt[p[j]],T.rt[f[lca]],r,mx,1,mx);
if (a1!=-1) ans=cmin(ans,abs(a1-r));
if (a2!=-1) ans=cmin(ans,abs(a2-r));
}
printf("%d\n",lst=ans);
}
return 0;
}
}
int main() {return nanfeng::main();}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章