题意：一棵树，求出每一个点到1的路径上的最大gcd,可以使一个变成0;
思路：保存一个数组为都取，然后每一个点维持一个vector数组，保存的是上一个的结果。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define fi first #define se second #define INF 0x3f3f3f3f #define clr(x,y) memset(x,y,sizeof x) #define PI acos(-1.0) #define ITER set<int>::iterator const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; vector<int>g[maxn]; int a[maxn],b[maxn],ans[maxn]; set<int>s[maxn]; int gcd(int x,int y){return y ? gcd(y,x % y) : x;} bool vis[maxn]; void dfs(int u) { vis[u] = true; for(int i = 0; i < g[u].size(); i ++) { int v = g[u][i];if(vis[v])continue; b[v] = gcd(b[u],a[v]);s[v].insert(b[u]); for(ITER it = s[u].begin(); it != s[u].end(); it ++)s[v].insert(gcd(a[v],*it)); dfs(v); } } int main() { int n,m; while( ~ scanf("%d",&n)) { clr(vis,false);for(int i = 0; i <= n; i ++)s[i].clear(); for(int i = 1; i <= n;i ++)g[i].clear(); for(int i = 1; i <= n;i ++)cin >> a[i]; for(int i = 1; i <= n - 1;i ++) { int x,y;scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x); } b[1] = a[1];s[1].insert(0); dfs(1); cout << a[1];printf("%c",n == 1 ? '\n' : ' '); for(int i = 2; i <= n;i ++)printf("%d%c",* (--s[i].end()),i < n ? ' ':'\n'); } return 0; }
