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;
}