这题我个人觉得是有问题的. (修改,这题没问题,set也不是暴力,而是去重作用.因为真正的gcd,不会太多.) 想了很久,感觉想不出下至n上至nlogn的算法,非常难受,然后上网看题解,发现居然是一个暴力,遍历所有情况,居然不会超时,n^2logn的也行,真是无言以对.既然这样,这题也失去了意义. (好在我没打这场比赛啊,A题都过不了,b题估计也要wa个好几次,C就跟别提了,少说要掉100分,T_T)
/* xzppp */ #include <iostream> #include <vector> #include <cstdio> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <string> #include <cmath> #include <set> using namespace std; #define FFF freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define MP make_pair #define PB push_back typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int > pii; const int MAXN = 2*1e5+17; const int MAXM = 20; const int MAXV = 1001+17; const int INF = 0x7fffffff; const int MOD = 1e9+7; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int a[MAXN]; vector<int > G[MAXN]; set<int > s[MAXN]; int vis[MAXN]; void dfs(int cur,int pre,int all) { if(vis[cur]) return; vis[cur] = 1; for (set<int>::iterator i = s[pre].begin(); i != s[pre].end(); ++i) s[cur].insert(gcd(a[cur],*i)); s[cur].insert(all); all = gcd(all,a[cur]); for (int i = 0; i < G[cur].size(); ++i) dfs(G[cur][i],cur,all); } int main() { #ifndef ONLINE_JUDGE FFF #endif int n; cin>>n; for (int i = 0; i < n; ++i) { scanf("%d",a+i); } for (int i = 0; i < n-1; ++i) { int u,v; scanf("%d%d",&u,&v); u--;v--; G[u].PB(v); G[v].PB(u); } dfs(0,0,0); s[0].insert(a[0]); for (int i = 0; i < n; ++i) { printf("%d\n",*s[i].rbegin()); } return 0; }