CF1101D?GCD Counting?

又被trick了

不用什么點(diǎn)分治

直接樹形dp即可

開始的想法：

f[x][j]x為根的子樹gcd至少為j（j是x的一個(gè)約數(shù)）的最長鏈

然后對(duì)y合并。類似于樹的直徑

但是復(fù)雜度還是很大的。。。

?

這個(gè)題的關(guān)鍵是：我們只關(guān)心gcd是不是1，并不關(guān)心gcd是什么！

gcd不是1，意味著一定有公共質(zhì)因子！

而質(zhì)因子個(gè)數(shù)非常少

可以f[x][j]表示，x為根的子樹，往下走，公共質(zhì)因子為j的最長鏈

然后甚至可以暴力合并！

顯然最優(yōu)解可以被處理到！

?

代碼：

#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } namespace Miracle{ const int N=2e5+5; vector<int>p[N],f[N]; int n; int ans; struct node{int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt; } void dfs(int x,int fa){for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa) continue;dfs(y,x);for(reg j=0;j<p[x].size();++j){// cout<<" j "<<p[x][j]<<endl;for(reg k=0;k<p[y].size();++k){// cout<<" k "<<p[y][k]<<endl;if(p[x][j]==p[y][k]){ans=max(ans,f[x][j]+f[y][k]);f[x][j]=max(f[x][j],f[y][k]+1);}}}} } void div(int x,int id){for(reg i=2;(ll)i*i<=x;++i){if(x%i==0){p[id].push_back(i);f[id].push_back(1);while(x%i==0) x/=i;}}if(x>1){p[id].push_back(x);f[id].push_back(1);} } int main(){rd(n);int x;bool flag=false;for(reg i=1;i<=n;++i){rd(x);if(x!=1) flag=true;div(x,i);}if(!flag){puts("0");return 0;}ans=1;int y;for(reg i=1;i<=n-1;++i){rd(x);rd(y);add(x,y);add(y,x);}dfs(1,0);printf("%d",ans);return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/1/17 19:37:47 */

總結(jié)：
其實(shí)有些時(shí)候，題目很麻煩

但是實(shí)際上可以簡化條件，想想我們關(guān)心什么

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10284269.html

總結(jié)

以上是生活随笔為你收集整理的CF1101D GCD Counting的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。