题目
描述 :
给出强制在线参数(k),树的大小(n)，和每个点的点权(a_i);
有(m)个询问，每个询问是$u ,d $ 的形式；
表示询问(u)为根的子树中，和(u)的距离不超过(d)的点的点权(lcm)；
范围：
$k in { 0,1 } , 1 le n , q le 100000 , a_i le 10000000 $;
题解
-
(lcm)不太好合并，首先一定是找到一种合理的方式去表示(lcm)；
-
考虑每个因子(p)，如果存在将(p,p^2,p^3,cdots)看成不同的颜色，每种颜色存在的贡献是将答案乘以(p);
-
对于每一种颜色，我们只需要维护一个树链并即可；
-
对每个颜色维护一个(set)，用来维护插入一个点树链并的修改；
-
对于非强制在线的情况，只需要将询问按(dep[u]+d)排序，线段树维护单点修改子树查询；
-
强制在线将线段树可持久化就好了；
-
时间复杂度和空间复杂度：(O(n log n log a_i)) ;
#include<bits/stdc++.h> #define pb push_back #define mod 998244353 #define ll long long using namespace std; const int N=100010,M=10000010; int n,m,k,a[N],b[N],o=1,hd[N],idx,st[N],ed[N],id[N],dep[N]; int f[N<<1][20],lg[N<<1],pos[N<<1],bin[20],idx2; int sz,rt[N],mul[N*600],ls[N*600],rs[N*600]; int vis[M],pr[M],pt,mn[M]; struct Edge{int v,nt;}E[N<<1]; set<int>s[N*30]; set<int>::iterator I,I1,I2; map<int,int>hsh; char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x; } void adde(int u,int v){ E[o]=(Edge){v,hd[u]};hd[u]=o++; E[o]=(Edge){u,hd[v]};hd[v]=o++; } void pre(){ mn[1]=1; for(int i=2;i<=1e7;++i){ if(!vis[i])mn[pr[++pt]=i]=i; for(int j=1,t;j<=pt&&i*pr[j]<=1e7;++j){ vis[t=i*pr[j]]=1;mn[t]=pr[j]; if(i%pr[j]==0)break; } } } void dfs(int u,int fa){ f[pos[u]=++idx2][0]=u; id[st[u]=++idx]=u; dep[u]=dep[fa]+1; for(int i=hd[u];i;i=E[i].nt){ int v=E[i].v; if(v==fa)continue; dfs(v,u); f[++idx2][0]=u; } ed[u]=idx; } int Min(int x,int y){return dep[x]<dep[y]?x:y;} void init(){ lg[0]=-1;for(int i=1;i<=idx2;++i)lg[i]=lg[i>>1]+1; for(int i=bin[0]=1;i<=18;++i)bin[i]=bin[i-1]<<1; for(int i=1;i<=18;++i) for(int j=1;j+bin[i]-1<=idx2;++j){ f[j][i]=Min(f[j][i-1],f[j+bin[i-1]][i-1]); } } int lca(int u,int v){ int x=pos[u],y=pos[v]; if(x>y)swap(x,y); int t=lg[y-x+1]; return Min(f[x][t],f[y-bin[t]+1][t]); } bool cmp(const int&x,const int&y){return dep[x]<dep[y];} int get(int x){ if(!hsh[x])return hsh[x]=++idx; return hsh[x]; } int pw(int x,int y){ int re=1; while(y){ if(y&1)re=(ll)re*x%mod; y>>=1;x=(ll)x*x%mod; } return re; } void ins(int&k,int lst,int l,int r,int x,int y){ mul[k=++sz]=(ll)mul[lst]*y%mod; ls[k]=ls[lst],rs[k]=rs[lst]; if(l==r)return; int mid=l+r>>1; if(x<=mid)ins(ls[k],ls[lst],l,mid,x,y); else ins(rs[k],rs[lst],mid+1,r,x,y); } int query(int k,int l,int r,int x,int y){ if(l==x&&r==y)return mul[k]; int mid=l+r>>1; if(y<=mid)return query(ls[k],l,mid,x,y); else if(x>mid)return query(rs[k],mid+1,r,x,y); else return (ll)query(ls[k],l,mid,x,mid)*query(rs[k],mid+1,r,mid+1,y)%mod; } int main(){ freopen("half.in","r",stdin); freopen("half.out","w",stdout); pre(); k=rd();n=rd(); for(int i=1;i<=n;++i)a[i]=rd(),b[i]=i; for(int i=1;i<n;++i)adde(rd(),rd()); dfs(1,0); init(); sort(b+1,b+n+1,cmp); mul[0]=1;idx=0; for(int i=1;i<=n;++i){ int u=b[i],d=dep[u],tmp=a[u]; rt[d]=rt[dep[b[i-1]]]; while(tmp!=1){ int x=mn[tmp],ix=pw(x,mod-2),y,z=1; while(tmp%x==0&&(tmp/=x)){ y=get(z*=x); s[y].insert(st[u]); I=s[y].lower_bound(st[u]); I1=I;if(I!=s[y].begin())--I1; I2=I;++I2; ins(rt[d],rt[d],1,n,st[u],x); int u1=0,u2=0,t; if(I!=s[y].begin()){ u1=id[*I1];t=lca(u1,u); ins(rt[d],rt[d],1,n,st[t],ix); } if(I2!=s[y].end()){ u2=id[*I2];t=lca(u2,u); ins(rt[d],rt[d],1,n,st[t],ix); } if(u1&&u2){ t=lca(u1,u2); ins(rt[d],rt[d],1,n,st[t],x); } } } } for(int i=dep[b[n]]+1;i<=n;++i)rt[i]=rt[i-1]; m=rd(); int ans=0; for(int i=1,u,d;i<=m;++i){ u=rd()^(k*ans);d=min(n,dep[u]+rd()^(k*ans)); ans=query(rt[d],1,n,st[u],ed[u]); printf("%d ",ans); } return 0; }