cd1101d 简单dp

链接

思路

所有数的质因数存下来，最多6个。

然后\(f[i][j][0/1]\)表示i子树内链gcd为j的i是否为链头。

暴力转移就行了

代码

#include <bits/stdc++.h>

using namespace std;

const int _=2e5+7,N=2e5;

int n,pri[_],vis[_],cnt;

vector<int> G[_],dsr[_];

unordered_map<int,int> id[_];

void Euler() {

	for(int i=2;i<=N;++i) {

		if(!vis[i]) {

			pri[++cnt]=i;

			for(int j=i+i;j<=N;j+=i) vis[j]=1;

		}

	}

}

int f[_][7][2],ans=0;

void dfs(int u,int fa) {

	for(int i=0;i<(int)dsr[u].size();++i) f[u][i][0]=f[u][i][1]=1;

	int las[7]={};

	for(auto v:G[u]) {

		if(v==fa) continue;

		dfs(v,u);

		for(auto x:dsr[u]) {

			if(id[v].count(x)) {

				int a=id[u][x],b=id[v][x];

				f[u][a][1]=max(f[u][a][1],f[v][b][0]+las[a]+1);

				las[a]=max(las[a],f[v][b][0]);

				f[u][a][0]=max(f[u][a][0],f[v][b][0]+1);

			}

		}

	}

	for(int i=0;i<(int)dsr[u].size();++i) ans=max(ans,f[u][i][1]);

}

int main() {

	// freopen("a.in","r",stdin);

	Euler();scanf("%d",&n);

	for(int i=1,val,js;i<=n;++i) {

		scanf("%d",&val),js=0;

		for(int j=1;pri[j]*pri[j]<=cnt;++j) {

			if(val%pri[j]==0) {

				dsr[i].push_back(pri[j]),id[i][pri[j]]=js++;

				while(!(val%pri[j])) val/=pri[j];

			}

		} if(val!=1) dsr[i].push_back(val),id[i][val]=js++;

	}

	for(int i=1,u,v;i<n;++i) {

		scanf("%d%d",&u,&v);

		G[u].push_back(v),G[v].push_back(u);

	}

	dfs(1,0);

	cout<<ans<<"\n";

	return 0;

}

巴特西

cd1101d 树形dp

cd1101d 简单dp

链接

思路

代码

最新文章

热门文章