Codeforces ECR #058 : D. GCD Counting

DとEの難易度が反転した回。
https://codeforces.com/contest/1101/problem/D

問題

木を成すグラフが与えられる。
各頂点には200000以下の正整数が設定されている。
この木の上のパスのうち、通過する頂点上の設定値のGCDが2以上になる最長の長さを求めよ。

解法

各素数について、その素数の倍数であるような部分グラフに対し最長パスを求めればよいというのは容易に想像がつく。
最長パス自体は良くある典型木DPなので説明は省略するとしても、200000以下の素数全部について毎回グラフを探索すると間に合わない。
よって、各頂点について設定値のその素因数に対してのみ、SbuTree内のその頂点を含む最長パスを探索・更新していこう。

const int prime_max = 200000;
int NP,prime[100000],divp[prime_max];

int N;
vector<int> C[202020];
vector<int> E[202020];
map<int,int> M[202020];
int ret;


void dfs(int cur,int pre) {
	FORR(c,C[cur]) M[cur][c]=1;
	
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		
		FORR(c,C[cur]) {
			ret=max(ret,M[cur][c]+M[e][c]);
			M[cur][c]=max(M[cur][c],M[e][c]+1);
		}
		
	}
	
	FORR(c,C[cur]) ret=max(ret,M[cur][c]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		for(j=2;j*j<=200000;j++) if(x%j==0) {
			C[i].push_back(j);
			while(x%j==0) x/=j;
		}
		if(x>1) C[i].push_back(x);
		sort(ALL(C[i]));
	}
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	cout<<ret<<endl;
	
	
}

まとめ

この回Eの難易度設定が謎すぎた。