[Codeforces] 842C. Ilya And The Tree

題目連結:http://codeforces.com/contest/842/problem/C

---

一直以為因數個數會太多，所以只打算枚舉質因數....
但其實直接枚舉因數，然後看看哪個因數個數有超過n-1個之類的就好，枚舉完後把他插進去，讓下面的人來看。(頭痛，有點不知所云OAO

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
const int C = 200000 + 5;
const int N = 200000 + 5;

vector<int> frac[C], G[N];
int arr[N], ans[N], cnt[C];

void sieve(int);
void dfs(int,int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	sieve(C);
	int n; cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	for(int i=1;i<n;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	dfs(1, 1, 0, 0);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
	return 0;
}

void sieve(int n){
	for(int i=2;i<n;i++) for(int j=i;j<n;j+=i){
		frac[j].PB(i);
	}
}

void dfs(int w, int f, int g, int d){
	auto& ret = ans[w];
	for(auto i: frac[arr[w]]){
		if(cnt[i] >= d-1) ret = i;
		cnt[i]++;
	}
	ret = max(ret, g);
	g = __gcd(g, arr[w]);
	for(auto i: G[w]){
		if(i==f) continue;
		dfs(i, w, g, d+1);
	}
	for(auto i: frac[arr[w]]){
		cnt[i]--;
	}
}