9022: TeaTree
时间限制: 3 Sec 内存限制: 1024 MB提交: 15 解决: 8
[提交] [状态] [命题人:admin]
题目描述
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.
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
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.
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> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int 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]); return 0; }