C. Ilya And The Tree 树形dp 暴力

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 4e5 + 10;
typedef long long ll;
int dp[maxn],head[maxn],cnt = 0,a[maxn];
vector<int>vec[maxn];
struct node
{
    int u,v,nxt;
    node(int u=0,int v=0,int nxt=0):u(u),v(v),nxt(nxt){}
}ex[maxn];

void init()
{
    memset(head,-1,sizeof(head));
    cnt = 0;
}
void add(int u,int v)
{
    ex[cnt] = node(u,head[u]);
    head[u] = cnt++;
    ex[cnt] = node(v,u,head[v]);
    head[v] = cnt++;
}

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a%b);
}

void dfs(int u,int pre)
{
    for(int i=head[u];i!=-1;i=ex[i].nxt)
    {
        int v = ex[i].v;
        if (v == pre) continue;
        dp[v] = gcd(dp[u],a[v]);
        vec[v].push_back(dp[u]);
        for(int j=0;j<vec[u].size();j++) vec[v].push_back(gcd(vec[u][j],a[v]));
        sort(vec[v].begin(),vec[v].end());
        vec[v].erase(unique(vec[v].begin(),vec[v].end()),vec[v].end());
        dfs(v,u);
    }
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dp[1] = a[1];
    vec[1].push_back(0);
    dfs(1,-1);
    for (int i = 1; i <= n; i++) dp[i] = max(dp[i],vec[i].back());
    for (int i = 1; i <= n; i++) printf("%d ",dp[i]);
    return 0;
}