# ShanLunjiaJian的blog

### CF1292D Chaotic V. 题解

posted on 2021-01-28 09:27:21 | under 题解 |

### 2.求LCA

\begin{aligned} 15&=(0,1,1,0,...)\\ 20&=(2,0,1,0,...)\\ \operatorname{LCA}(15,20)=5&=(0,0,1,0,...)\\ \end{aligned}

### 4.判断祖先关系

#include<stdio.h>
#include<string.h>

int n;
int b[5002],prime[700],pcnt;
int temp[5002],val[20002];
int cnt;
long long ans=0x7fffffffffffffff;

struct Num
{
int e[700];
Num(){ memset(e,0,sizeof(e)); }
inline bool operator == (Num x)
{
for(int i=1;i<=pcnt;i++)
if(e[i]!=x.e[i]) return 0;
return 1;
}
inline bool operator < (Num x)
{
for(int i=1;i<=pcnt;i++)
if(e[i]!=x.e[i])
if(e[i]<x.e[i]) return 1;
else return 0;
return 0;
}
}a[20000];

inline void init()
{
for(int i=2;i<=5000;i++)
if(!b[i])
{
prime[++pcnt]=i;
for(int j=2*i;j<=5000;j+=i)
b[j]=1;
}

for(int i=1;i<=5000;i++) temp[i]=i;
for(int i=1;i<=pcnt;i++)
for(int j=1;j<=5000;j++)
while(temp[j]%prime[i]==0)
temp[j]/=prime[i],a[j].e[i]++;
for(int i=1;i<=5000;i++)
for(int j=1;j<=pcnt;j++)
a[i].e[j]+=a[i-1].e[j];
cnt=5000;
}

struct Edge
{
int v,w,next;
}e[100002];

int h[50002];
int ecnt;

inline void add_edge(int u,int v,int w)
{
e[++ecnt]={v,w,h[u]};
h[u]=ecnt;
e[++ecnt]={u,w,h[v]};
h[v]=ecnt;
}

#define min(x,y) ((x)<(y)?(x):(y))

inline Num lca(Num a,Num b)
{
Num c;
int i=pcnt;
for(;a.e[i]==b.e[i];i--) c.e[i]=a.e[i];
c.e[i]=min(a.e[i],b.e[i]);
i--;
for(;i>0;i--) c.e[i]=0;
return c;
}

inline int dist(Num u,Num v)//jump from u to v
{
int res=0;
for(int i=1;i<=pcnt;i++)
res+=u.e[i]-v.e[i];
return res;
}

inline bool is_son(Num u,Num v)//check if u is v's son
{
int i=1;
for(;i<=pcnt&&!v.e[i];i++);
if(i>pcnt) return 1;
if(v.e[i]>u.e[i]) return 0;
i++;
for(;i<=pcnt;i++)
if(v.e[i]!=u.e[i]) return 0;
return 1;
}

int s[20002],top;

inline void insert(int u)
{
a[++cnt]=lca(a[s[top]],a[u]);
if(!(a[cnt]==a[s[top]]))
{
while(is_son(a[s[top-1]],a[cnt])&&!(a[s[top-1]]==a[cnt]))
if(!(a[cnt]==a[s[top-1]]))
else
}
s[++top]=u;
}

inline void build()
{
s[++top]=1;
for(int i=2;i<=5000;i++)
if(val[i])
insert(i);
for(int i=1;i<top;i++)
}

bool vis[20002];
int sum[20002];
long long dp[20002],f[20002];

void dfs1(int u,int fa)
{
vis[u]=1;
sum[u]=val[u];
f[u]=0;
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=fa)
dfs1(e[i].v,u),sum[u]+=sum[e[i].v],f[u]+=(long long)e[i].w*sum[e[i].v]+f[e[i].v];
}

void dfs2(int u,int fa)
{
for(int i=h[u];i;i=e[i].next)
if(e[i].v!=fa)
dp[e[i].v]=(dp[u]-(f[e[i].v]+(long long)e[i].w*sum[e[i].v])+(long long)e[i].w*(sum[1]-sum[e[i].v])+f[e[i].v]),
dfs2(e[i].v,u);
}

int main()
{
scanf("%d",&n);
for(int i=1,k;i<=n;i++)
scanf("%d",&k),k==0?val[1]++:val[k]++;
init();
build();
dfs1(1,0);
dp[1]=f[1];
dfs2(1,0);
for(int i=1;i<=cnt;i++)
if(vis[i]) ans=min(ans,dp[i]);
printf("%I64d",ans);
return 0;
}