Codeforces #264 Div2 E. Caisa and Tree

ちょっと手こずったけど何とか解けた。
http://codeforces.com/contest/463/problem/E

問題

N頂点からなる根付の木を成すグラフと、各頂点の値A[i]が与えられる。
以下のQ個のクエリに答えよ。

1. 頂点xが与えられるので、根からxにたどるパス上の頂点vのうち、A[v]とA[x]が2以上の公約数を持つような頂点vを答えよ。候補が複数あるなら、最もxに近いものを答えよ。
2. 頂点xと整数yが与えられるので、A[x]をyに更新せよ。ただしこのクエリは50個以下しかない。

解法

初期状態またはタイプ２のクエリを行うたびに、全頂点におけるクエリ１の回答を一斉に更新しておく。
あとはクエリ１ごとに計算済みの回答を出力するだけ。

A[i]の範囲は1～2000000までであり、この間の素数は150K個以下である。
まずA[i]を全部素因数分解しておく(タイプ２の時は更新した頂点だけ再計算すればよい)。

この状態で木のDFSを行う。
その際、150K個の素数に対応した配列を準備し、各素数の値を持つもっとも深い頂点の番号を更新しながらDFSを進めればよい。
今見ている頂点のA[i]の素因数について、配列を見て他の頂点番号が入っていればそれが答えの候補になる。

150K個の素数というと多いけど、各頂点で見るべき素数はせいぜい6個まで(2*3*5*7*11*13)なので割と軽い。
タイプ１のクエリ回数をQ1、タイプ２のクエリ回数をQ2とすると、最初の素因数分解とDFSでO(N*√maxA)、タイプ１クエリの処理がO(Q1)、タイプ２クエリの処理がO(Q2*(√maxA+N*P))程度で済む。(PはmaxA以下の整数の最大素因数数)

int N,Q;
vector<int> E[100020];
int R[100020],BR[200010];

const int prime_max = 2000001;
int NP,divp[prime_max];
int DP[200000];
vector<ll> pr[100010];
map<int,int> M;

vector<ll> enumdiv(ll n) {
	vector<ll> V;
	for(ll i=2;i*i<=n;i++) {
		if(n%i==0) V.push_back(M[(int)i]);
		while(n%i==0) n/=i;
	}
	if(n>1) V.push_back(M[(int)n]);
	return V;
}

void build(int cur,int pre,int dep) {
	vector<int> PP;
	int i;
	DP[dep]=cur+1;
	R[cur]=-1;
	FOR(i,pr[cur].size()) {
		int t=pr[cur][i];
		R[cur]=max(R[cur],BR[t]);
		PP.push_back(BR[t]);
		BR[t]=dep;
	}
	if(R[cur]>=0) R[cur]=DP[R[cur]];
	
	FOR(i,E[cur].size()) if(pre!=E[cur][i]) build(E[cur][i],cur,dep+1);
	FOR(i,pr[cur].size()) BR[pr[cur][i]]=PP[i];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;i<prime_max;i++) if(divp[i]==0) {
		M[i]=NP++;
		for(j=i;j<prime_max;j+=i) divp[j]=i;
	}
	
	cin>>N>>Q;
	FOR(i,N) cin>>x, pr[i]=enumdiv(x);
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	MINUS(BR);
	build(0,-1,1);
	
	while(Q--) {
		cin>>i>>x;
		x--;
		if(i==1) {
			cout << R[x] <<endl;
		}
		else {
			cin>>y;
			pr[x]=enumdiv(y);
			MINUS(BR);
			build(0,-1,1);
		}
	}
}

まとめ

問題の読み間違いで無駄なミスをしてしまった…。