https://codeforces.com/contest/990/problem/G
2e5以内,能够形成的gcd非常有限,一条链内至多也就是log2e5个,
因此可以暴力点分治+子树合并,虽然复杂度比线性做法多了一个log,但是不怎么费脑子
复杂度大约是$100*nlogn$,
其实还有很多优化空间,比如gcd为1就跳出dfs_dis之类的
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(i,x,g,e) for(int i=g[x];i;i=e[i].next)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define show(x) cout<<#x<<"="<<x<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<"="<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa2(x,a,b) cout<<#x<<": ";rep(i,a,b) cout<<x[i]<<' ';cout<<endl
using namespace std;//head
using namespace __gnu_pbds;
const int maxn=2e5+10,maxm=2e6+10;
const ll INF=0x3f3f3f3f,mod=1e9+7;
int casn,n,m,k;
int val[maxn];
namespace graph{
vector<int>g[maxn];
int all,sz[maxn],root,maxt;
bool vis[maxn];
int dfs_root(int now,int fa){
int cnt=1;
for(auto to:g[now]){
if(to==fa||vis[to])continue;
cnt+=dfs_root(to,now);
}
int tmp=max(cnt-1,all-cnt);
if(maxt>tmp) maxt=tmp,root=now;
return sz[now]=cnt;
}//@基础部分@
ll ans[maxn];
int dis[maxn],dfn,cnt[maxn],gcd[maxn],tot;
void dfs_dis(int now,int fa,int d){
dis[++dfn]=d;
for(auto to:g[now]){
if(to==fa||vis[to]) continue;
dfs_dis(to,now,__gcd(d,val[to]));
}
}
void cal(int now){
tot=1;
gcd[1]=val[now];
cnt[val[now]]=1;
for(auto to:g[now]){
if(vis[to]) continue;
dfn=0;
dfs_dis(to,now,__gcd(val[now],val[to]));
rep(i,1,dfn){
int x=dis[i];
rep(j,1,tot)ans[__gcd(gcd[j],x)]+=cnt[gcd[j]];
}
rep(i,1,dfn){
if(!cnt[dis[i]]) gcd[++tot]=dis[i];
cnt[dis[i]]++;
}
}
rep(i,1,tot) cnt[gcd[i]]=0;
ans[val[now]]++;
}
void dfs_dv(int now){
vis[now]=1;
cal(now);
for(auto to:g[now]){
if(vis[to]) continue;
all=sz[to],maxt=1e9,root=n+1;
dfs_root(to,now);
dfs_dv(root);
}
}
void solve(int n){
all=n,maxt=1e9;
dfs_root(1,1);
dfs_dv(root);
}
}
using namespace graph;
int main() {IO;
cin>>n;
rep(i,1,n) cin>>val[i];
rep(i,2,n){
int a,b;cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
solve(n);
rep(i,1,2e5){
if(ans[i]) cout<<i<<' '<<ans[i]<<'\n';
}
}
转载于:https://www.cnblogs.com/nervendnig/p/11623284.html