yukicoder : No.3250 最小公倍数

ちょっと定数倍厳しすぎないですかね…。
https://yukicoder.me/problems/no/3250

問題

根付き木が与えられる。
各点には正整数が設定されている。

木の各頂点に対し、Subtree内の全頂点に設定された値のLCMを答えよ。

解法

LCMを素因数分解した形で持ち、DFSしながらマージテクで子頂点のLCM同士のLCMを求めて行こう。
頂点数や設定値が微妙に大きいので、気を付けないとTLEする。

int N;
vector<int> E[505050];
map<int,int> dp[505050];
int V[1<<20];
ll A[1<<19];
ll ret[1<<19];
const ll mo=998244353;

vector<int> mul[1<<20];
const int MA=1000001;
void dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		if(dp[e].size()>dp[cur].size()) {
			swap(dp[cur],dp[e]);
			ret[cur]=ret[e];
		}
		FORR2(a,b,dp[e]) {
			if(dp[cur][a]<b) {
				(ret[cur]*=mul[a][b-dp[cur][a]-1])%=mo;
				dp[cur][a]=b;
			}
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,MA) V[i]=i;
	for(i=2;i<MA;i++) if(V[i]==i) {
		mul[i].push_back(i);
		while(mul[i].back()*i<MA) mul[i].push_back(mul[i].back()*i);
		if(i<=1000) for(j=i*i;j<MA;j+=i) V[j]=i;
	}
	
	cin>>N;
	FOR(i,N) {
		cin>>ret[i];
		x=ret[i];
		while(x>1) {
			dp[i][V[x]]++;
			x/=V[x];
		}
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	FOR(i,N) cout<<ret[i]<<"\n";
	
	
}

まとめ

想定解だと思うけど最初TLE連発した…。