成都大型网站设计公司,网站名怎么写,建设银行的网站用户名,北京网站推广cd1101d 简单dp 链接 codeforces 思路 所有数的质因数存下来#xff0c;最多6个。 然后\(f[i][j][0/1]\)表示i子树内链gcd为j的i是否为链头。 暴力转移就行了 代码 #include bits/stdc.h
using namespace std;
const int _2e57,N2e5;
int n,pri[_],vis[_],cnt;
vector… cd1101d 简单dp 链接 codeforces 思路 所有数的质因数存下来最多6个。 然后\(f[i][j][0/1]\)表示i子树内链gcd为j的i是否为链头。 暴力转移就行了 代码 #include bits/stdc.h
using namespace std;
const int _2e57,N2e5;
int n,pri[_],vis[_],cnt;
vectorint G[_],dsr[_];
unordered_mapint,int id[_];
void Euler() {for(int i2;iN;i) {if(!vis[i]) {pri[cnt]i;for(int jii;jN;ji) vis[j]1;}}
}
int f[_][7][2],ans0;
void dfs(int u,int fa) {for(int i0;i(int)dsr[u].size();i) f[u][i][0]f[u][i][1]1;int las[7]{};for(auto v:G[u]) {if(vfa) continue;dfs(v,u);for(auto x:dsr[u]) {if(id[v].count(x)) {int aid[u][x],bid[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 i0;i(int)dsr[u].size();i) ansmax(ans,f[u][i][1]);
}
int main() {// freopen(a.in,r,stdin);Euler();scanf(%d,n);for(int i1,val,js;in;i) {scanf(%d,val),js0;for(int j1;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 i1,u,v;in;i) {scanf(%d%d,u,v);G[u].push_back(v),G[v].push_back(u);}dfs(1,0);coutans\n;return 0;
} 转载于:https://www.cnblogs.com/dsrdsr/p/11405984.html
