竟然A了 23333，复杂度真的是玄学
最大复杂度n根号loglog，但其实复杂度远没这么大，后来一想A了正常
首先，复杂度计算的是错的，没有根号，n即是最大约数的个数
第二，考虑到轻链一开始是很小的，而1e5以内的约数个数最多的数只有60+个约数
第三，轻链在向重链合并的时候，很多因数是被重复的，计算量大大减小，或者换一种理解方式，很难打满1e5个因数。
以后感觉树上做不了的题，都拿DSU试试（雾
其实并不是玄学，可以证明的。
DSU真是个好东西。
里边只有一点还没自己证出，就是一棵树的重链最多为log个，以后慢慢理解。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int ver[N],head[N],Next[N],A[N],ans[N],sz[N],dsu[N],tot,t; unordered_set<int> a[N/2]; vector<int> b[N/2]; void add(int x,int y){ ver[++tot]=y,Next[tot]=head[x],head[x]=tot; } void init(){ for(int i=1;i<=100000;++i){ for(int j=i;j<=100000;j+=i){ b[j].push_back(i); } } } void mrg(int x,int y,int z){ for(auto& i : a[z]){ if(a[y].find(i)!=a[y].end()) ans[x]=max(ans[x],i); a[y].insert(i); } } void dfs(int x=1){ sz[x]=1; if(head[x]==0){ dsu[x]=++t;ans[x]=-1; for(auto& i : b[A[x]])a[t].insert(i); return; } int big=0; for(int i=head[x];i;i=Next[i]){ dfs(ver[i]);sz[x]+=sz[ver[i]]; if(sz[ver[i]]>sz[big])big=ver[i]; } dsu[x]=dsu[big],ans[x]=-1; for(int i=head[x];i;i=Next[i]){ if(ver[i]!=big){ mrg(x,dsu[x],dsu[ver[i]]); } } for(auto& i : b[A[x]]){ if(a[dsu[x]].find(i)!=a[dsu[x]].end())ans[x]=max(ans[x],i); else a[dsu[x]].insert(i); } } int main(){ //freopen("1.txt","r",stdin); init(); ios::sync_with_stdio(0); int n,x;cin>>n; for(int i=2;i<=n;++i)cin>>x,add(x,i); for(int i=1;i<=n;++i)cin>>A[i]; dfs(); for(int i=1;i<=n;++i)printf("%d\n",ans[i]); }
