Fork me on GitHub

图+dfs+gcd

发表于 | 分类于 | 热度 ℃  |  
字数统计 670 字 | 阅读时长 4 分钟

最近在做codeforces上面的题，感觉质量挺高的，而且区分难易，便于入手。今天做到的这题考察的东西不少，由于本人水平不济（其实是懒），只能看看别人写的代码，找到一个写的挺好的，多多学习。

原题链接：Ilya And The Tree

Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex i is equal to ai.

Ilya believes that the beauty of the vertex x is the greatest common divisor of all numbers written on the vertices on the path from the root to x, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.

For each vertex the answer must be considered independently.

The beauty of the root equals to number written on it.

Input

First line contains one integer number n — the number of vertices in tree (1 ≤ n ≤ 2·105).

Next line contains n integer numbers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 2·105).

Each of next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n, x ≠ y), which means that there is an edge (x, y) in the tree.

Output

Output n numbers separated by spaces, where i-th number equals to maximum possible beauty of vertex i.

Examples

input

1
2
3
2
6 2
1 2

output

1
6 6

input

1
2
3
4
3
6 2 3
1 2
1 3

output

1
6 6 6

input

1
2
1
10

output

1
10

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int MAXV=500000+3;
int V, a[MAXV];
vector<int> G[MAXV];//图的邻接矩阵表示
int path[MAXV];//从根节点到当前结点路径的gcd，没用0
vector<int> dp[MAXV];//从根节点到当前结点所有可以得到的gcd，用了0
void dfs(int u, int fa)
{
    if(~fa)//非根节点
    {
        path[u]=__gcd(path[fa], a[u]);
        dp[u].push_back(path[fa]);//把当前结点的权值变成0
        for(int i=0;i<dp[fa].size();++i)
            dp[u].push_back(__gcd(dp[fa][i], a[u]));
        sort(dp[u].begin(), dp[u].end());
        dp[u].erase(unique(dp[u].begin(), dp[u].end()), dp[u].end());//去重
    }
    else//根节点
    {
        path[u]=a[u];
        dp[u].push_back(0);
        dp[u].push_back(a[u]);
    }
    for(int i=0;i<G[u].size();++i)
        if(G[u][i]!=fa)
            dfs(G[u][i], u);
}
int main()
{
    scanf("%d", &V);
    for(int i=1;i<=V;++i)
        scanf("%d", &a[i]);
    for(int i=1;i<V;++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1);
    for(int i=1;i<=V;++i)
        printf("%d%c", dp[i].back(), i==V?'\n':' ');
    return 0;
}

转自：http://blog.csdn.net/yasola/article/details/77711827

知识点补充：

  1. ~-1的结果是0。

  2. if(一个负数) 是会运行后面的语句的。

  3. __gcd(a,b)今后直接拿来用，省得自己写了。

  4. sort(dp[u].begin(), dp[u].end());

    dp[u].erase(unique(dp[u].begin(), dp[u].end()), dp[u].end());//去重

    注意unique的用法，使用前要先排序，配合erase使用效果很好。

    ​

donate the author