hdu6430
题意,对于每个点,求出它的子树中任意一点(包括该点)的lca为该点的最大的gcd(v[i],v[j])
由于的大小只有1e5,显然可以用欧拉筛预处理
void get(int n){ for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) v[j].push_back(i); }
然后从子树往父节点进行线段树合并即可,维护sum[N * 300]表示每个子节点处因子的出现次数,在合并时,如果父节点与子节点在该点处均有值,即可更新,然后sum[fa] += sum[son]
完整代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10,M=N*400; int n,up,rt[N],lc[M],rc[M],sum[M],res[N],a[N],cnt,flag; vector<int> g[N],v[N]; void get(int n){for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) v[j].push_back(i);} void change(int &p,int l,int r,int x){ if(!p) p=++cnt; if(l==r){sum[p]++; return ;} int mid=l+r>>1; if(x<=mid) change(lc[p],l,mid,x); else change(rc[p],mid+1,r,x); } int merge(int x,int y,int l,int r){ if(!x||!y) return x+y; if(l==r){if(sum[x]&&sum[y]) res[flag]=max(res[flag],l); sum[x]+=sum[y]; return x;} int mid=l+r>>1; lc[x]=merge(lc[x],lc[y],l,mid); rc[x]=merge(rc[x],rc[y],mid+1,r); return x; } void dfs(int x){ for(int i=0;i<v[a[x]].size();i++) change(rt[x],1,up,v[a[x]][i]); for(auto to:g[x]){dfs(to); flag=x; rt[x]=merge(rt[x],rt[to],1,up);} } signed main(){ get(1e5); cin>>n; for(int i=2,x;i<=n;i++) scanf("%d",&x),g[x].push_back(i); for(int i=1;i<=n;i++) scanf("%d",&a[i]),up=max(up,a[i]); memset(res,-1,sizeof res); dfs(1); for(int i=1;i<=n;i++) printf("%d\n",res[i]); return 0; }