Dowemo

I think there's a problem.
For a long time, it's very hard to feel free to figure out what's going on to n, and it's very hard to see the answer to the web.
If I didn't play this game, I didn't have a problem, b. I had to be a good one for a couple of questions, c, and I'd not forget about it, but I'd like to drop 100.


/* 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("%dn",*s[i].rbegin());


 }


 return 0;


}









Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs