思路：比赛时，写了个树dp，情况考虑少了，赛后才知道gcd的个数是很少的，可以直接暴力，每访问到一个点可以直接去掉这个点或者不去掉这个点，两种情况。开个vector保存这个点gcd的情况，算完之后要去重。
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Size(x) (int)((x).size()) #define fi(x) ((x).first) #define se(x) ((x).second) #define Z(x) (*(x)) typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; using namespace std; inline void debug(char ch){for(int __ii = 0; __ii < 20; ++__ii)putchar(ch);printf("\n");} const double eps = 1e-8; #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int maxn = 21e5 + 10; vector<int> g[maxn]; int c[maxn]; vector<int> dp[maxn]; int gcd(int x, int y){ return !y ? x : gcd(y, x % y); } void dfs(int u, int f, int gg){ for(int i = 0; i < g[u].size(); ++i){ int v = g[u][i]; if(v == f) continue; dp[v].clear(); dp[v].push_back(gg); for(int j = 0; j < dp[u].size(); ++j){ dp[v].push_back(gcd(dp[u][j], c[v])); } sort(dp[v].begin(), dp[v].end()); dp[v].erase(unique(dp[v].begin(), dp[v].end()), dp[v].end()); int t = gcd(gg, c[v]); dfs(v, u, t); } } int main(){ int n; while(scanf("%d", &n) == 1){ for(int i = 1; i <= n; ++i) scanf("%d", &c[i]); for(int i = 0; i < n - 1; ++i){ int x, y; scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); } dp[1].push_back(0),dp[1].push_back(c[1]); dfs(1, -1, c[1]); int flag = 1; for(int i = 1; i <= n; ++i){ if(flag){ flag = 0; printf("%d", dp[i].back()); } else printf(" %d", dp[i].back()); } printf("\n"); } } /*/ 6 2 5 4 6 0 0 0 4 1 0 2 3 */