Codeforces 842C(DFS+Set)

Codeforces 842C
题意：给定一棵树和它各个点的权值，对于一个结点它的美丽值是指他到根的路径上所有点权值的最大公约数，对于每个结点到根的路径，可以修改一个点的权值到0，问每个点的最大美丽值

树上暴力即可。暴力每个点改0的情况。
进行DFS，维护$now$(根到路径上所有数的$gcd$), $p$($u$的父亲), $s_u$($u$的集合(答案集合))
如果当前节点不改0，则当前节点可以和前面改过0或者没改过0的答案结合
如果当前节点改0，则当前节点只能和前面没改过0的答案结合($now$的作用)

然后之后输出$s_u$最后一个元素($set$内自动从小到大排序)即可

由于每个数的因子是分散的$\sqrt n$个，所以几个数的$gcd$很快变$1$，即$set$内元素个数不多，所以能很快算出答案

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 2 * 100000 + 5; 
set<int> s[MAXN];
vector<int> G[MAXN];
int n, a[MAXN];
int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    return gcd(b, a % b);
}
void dfs(int u, int p, int now) {
    for (set<int>::iterator it = s[p].begin(); it != s[p].end(); it++) s[u].insert(gcd(*it, a[u]));//与前面改过或者没改过的答案结合
    s[u].insert(now);//与前面没改过的答案结合
    now = gcd(now, a[u]), s[u].insert(now);//和前面没改过0的答案结合
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (v != p) dfs(v, u, now);
    }
}
void clean() {}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int u, v, i = 1; i < n; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    dfs(1, 0, 0); 
    for (int i = 1; i <= n; i++) printf("%d ", *s[i].rbegin());
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}