[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]--;
	}
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology