Codeforces #848 : Div2 F. Maximizing Root

色々考えるなぁ。
https://codeforces.com/contest/1778/problem/F

問題

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

以下の処理をK回まで行うとき、根頂点の整数値を最大どこまで大きくできるか。

• 未選択の頂点vを選びvのsubtree内の頂点の整数値の公約数を、subtree内の各点の整数に掛ける

解法

dp(v,d) := (v自体に操作をする前に)vのsubtreeのGCDをdにするのにかかる操作回数
とする。dは高々vの約数の範囲を考えればよく、その範囲で子頂点から求めて行こう。

//-------------------------------------------------------

int T;
int N,K,A[202020];
vector<int> E[202020];
vector<int> C;
vector<int> M[40];
map<int,int> re;
int num[202020][40];

void dfs(int cur,int pre) {
	int i,x;
	FOR(i,C.size()) num[cur][i]=1<<20;
	int c=0;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		c++;
	}
	if(c==0) {
		num[cur][re[__gcd(A[0],A[cur]*A[cur])]]=1;
		num[cur][re[A[cur]]]=0;
	}
	else {
		FOR(i,C.size()) {
			int s=0;
			FORR(e,E[cur]) if(e!=pre) s=min(1<<20,s+num[e][i]);
			int v=__gcd(C[i],A[cur]);
			chmin(num[cur][re[v]],s);
			if(cur) chmin(num[cur][re[__gcd(A[0],v*v)]],s+1);
		}
	}
	
	FOR(x,C.size()) {
		FORR(d,M[x]) num[cur][x]=min(num[cur][x],num[cur][d]);
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) {
			cin>>A[i];
			A[i]=__gcd(A[i],A[0]);
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		C.clear();
		re.clear();
		for(i=1;i<=A[0];i++) if(A[0]%i==0) C.push_back(i);
		FOR(x,C.size()) {
			re[C[x]]=x;
			M[x].clear();
			for(y=x+1;y<C.size();y++) if(C[y]%C[x]==0) M[x].push_back(y);
		}
		dfs(0,0);
		int ma=A[0];
		FOR(x,C.size()) if(num[0][x]<K) ma=max(ma,C[x]*A[0]);
		cout<<ma<<endl;
	}
			
		
}

まとめ

問題名から一瞬平方根が絡むかと思ってしまった。