题意：一棵树，问每个点到1节点这条链的所有数字的gcd,可删除某个数，每个链单独处理
思路：暴力存，可删除重复的,可百度unique的具体用法
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e5+10; 4 5 int a[N],dp[N],b[N]; 6 vector<int > e[N],g[N]; 7 8 void dfs(int u,int fa){ 9 for(int i=0;i<e[u].size();i++){ 10 int v=e[u][i]; 11 if(v==fa) continue ; 12 dp[v]=__gcd(dp[u],a[v]); 13 g[v].push_back(dp[u]); 14 for(int j=0;j<g[u].size();j++) 15 g[v].push_back(__gcd(g[u][j],a[v])); 16 sort(g[v].begin(),g[v].end()); 17 g[v].erase(unique(g[v].begin(),g[v].end()),g[v].end()); 18 dfs(v,u); 19 } 20 } 21 22 int main(){ 23 int n; 24 scanf("%d",&n); 25 for(int i=1;i<=n;i++){ 26 scanf("%d",&a[i]); 27 } 28 for(int i=1;i<n;i++){ 29 int x,y; 30 scanf("%d%d",&x,&y); 31 e[x].push_back(y); 32 e[y].push_back(x); 33 } 34 dp[1]=a[1]; 35 g[1].push_back(0); 36 dfs(1,0); 37 for(int i=1;i<=n;i++){ 38 b[i]=dp[i]; 39 if(!g[i].empty()){ 40 b[i]=max(b[i],g[i].back()); 41 } 42 printf("%d ",b[i]); 43 } 44 printf(" "); 45 }