Problem E. TeaTree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Total Submission(s): 722    Accepted Submission(s): 255

Problem Description

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.

 

 

Input

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

 

 

Output

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.

 

求树上每点的一个值

这个值 是 该点 以及它的子树所有点的 最大gcd

 

#include 
      
       #include 
       
        #define rep(i,a,b) for(int i=a;i
        
         =b;i--)const int MX = 1e5;const int MXX = 400*MX;using namespace std;int n;vector
         
           G[MX+5],vv[MX+5];// init函数 实现将i因数分解 （i < 1e5）void init() {    rep(i,1,MX+1) vv[i].push_back(1);    rep(i,2,MX+1) {        vv[i].push_back(i);        for(int j=i+i;j<=MX;j+=i) vv[j].push_back(i);    }     // rep(i,1,MX+1) {    //     rep(j,0,vv[i].size()) {    //         printf("%d ",vv[i][j]);    //     }puts("");    // }}int root[MX+5],ls[MXX],rs[MXX],sum[MXX],rear,ans[MX];inline void push_up(int rt) {    if(ls[rt] && rs[rt]) sum[rt] = max(sum[ls[rt]],sum[rs[rt]]);    else if(ls[rt]) sum[rt] = sum[ls[rt]];    else if(rs[rt]) sum[rt] = sum[rs[rt]];}void update(int &rt,int l,int r,int p) {    if(rt==0) rt = ++rear;    if(l == r) {        sum[rt] = p;        return ;    }    int m = (l+r)>>1;    if(p <= m) update(ls[rt],l,m,p);    else update(rs[rt],m+1,r,p);    push_up(rt);}int merge(int rt, int prt, int &ans) {        if(rt==0 || prt==0) return rt^prt;        //这里维护最大的gcd        if(sum[rt] == sum[prt]) ans = max(ans,sum[rt]);        //这里只有有因子，就归并到rt上面        if(ls[rt] | ls[prt]) ls[rt] = merge(ls[rt], ls[prt], ans);        if(rs[rt] | rs[prt]) rs[rt] = merge(rs[rt], rs[prt], ans);        push_up(rt);        return rt;}void dfs(int u) {    ans[u] = -1;    rep(i, 0, G[u].size()) {        int v = G[u][i];        dfs(v);        root[u] = merge(root[u],root[v],ans[u]);    }}int main () {    freopen("in.txt" ,"r",stdin);    freopen("out.txt","w",stdout);    init();        scanf("%d", &n);    //建边    rep(i,2,n+1) {        int fa; scanf("%d",&fa);        G[fa].push_back(i);    }    //对每个v[i]建线段树    rear=0;    rep(i,1,n+1) {        int x; scanf("%d", &x);        root[i]=0;        rep(j, 0, vv[x].size()) {            update(root[i], 1, MX, vv[x][j]);        }    }    //暴力更新 gcd    dfs(1);    //输出答案    rep(i,1,n+1) printf("%d\n", ans[i]);    return 0;}