Recently, TeaTree acquire new knoledge gcd (Greatest Common Divisor), now she want to test you. As we know, TeaTree is a tree and her root is node 1, she have n nodes and n-1 edge, for each node i, it has it’s value v[i]. For every two nodes i and j (i is not equal to j), they will tell their Lowest Common Ancestors (LCA) a number : gcd(v[i],v[j]). For each node, you have to calculate the max number that it heard. some definition: In graph theory and computer science, the lowest common ancestor (LCA) of two nodes u and v in a tree is the lowest (deepest) node that has both u and v as descendants, where we define each node to be a descendant of itself.
输入
On the first line, there is a positive integer n, which describe the number of nodes. Next line there are n-1 positive integers f[2] ,f[3], …, f[n], f[i] describe the father of node i on tree. Next line there are n positive integers v[2] ,v[3], …, v[n], v[i] describe the value of node i. n<=100000, f[i]<i, v[i]<=100000
输出
Your output should include n lines, for i-th line, output the max number that node i heard. For the nodes who heard nothing, output -1.
样例输入
4
1 1 3
4 1 6 9
样例输出
2
-1
3
-1
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
usingnamespace std;
typedef longlong ll;
typedef pair<int, int> pii;
constint maxn = 1e5 + 10000;
int n,root[maxn],ls[maxn*400],rs[maxn*400],tot,w[maxn*400],res[maxn];
vector<int>v[maxn],re[maxn];
inline void init(){
for(register int i=1;i<maxn-108;++i){
for(register int j=1;j<=sqrt(i);++j){
if(i%j==0){
v[i].emplace_back(j);
if(j!=i/j){
v[i].emplace_back(i/j);
}
}
}
}
}
inline void update(int l,int r,int val,int &id){
if(!id)id=++tot;
if(l==r){
w[id]=val;
return;
}
int mid=l+r>>1;
if(val<=mid)update(l,mid,val,ls[id]);
else update(mid+1,r,val,rs[id]);
w[id]=max(w[ls[id]],w[rs[id]]);
}
inline int merge(int fa,int v,int &ans){
if(!fa||!v)return fa|v;
if(w[fa]==w[v])ans=max(ans,w[fa]);
if(ls[fa]||ls[v])ls[fa]=merge(ls[fa],ls[v],ans);
if(rs[fa]||rs[v])rs[fa]=merge(rs[fa],rs[v],ans);
return fa;
}
inline void dfs(int cur){
for(register int i=0;i<re[cur].size();++i){
int to=re[cur][i];
dfs(to);
merge(root[cur],root[to],res[cur]);
}
}
int main() {
//freopen("1.txt", "r", stdin); init();
scanf("%d",&n);
//printf("***");for(register int i=2,x;i<=n;++i){
scanf("%d",&x);
re[x].emplace_back(i);
}
for(register int i=1,val;i<=n;++i){
scanf("%d",&val);
for(register int j=0;j<v[val].size();++j){
update(1,1e5,v[val][j],root[i]);
}
}
for(register int i=1;i<=n;++i)res[i]=-1;
dfs(1);
for(register int i=1;i<=n;++i)printf("%d\n",res[i]);
return0;
}
