计蒜客 青云的机房组网方案
题目链接：青云的机房组网方案（困难） - 题库 - 计蒜客 (jisuanke.com)
注意到，\(a_i\) 的范围为 \([1,10^5]\)，又由于 \(2\times3\times5\times7\times11\times13=30030\)，所以 \(a\) 的质因数的种类最多只有 \(6\) 种。
然后我们考虑通过容斥计算答案。答案等于所有点对之间的距离减去不互质点对之间的距离。
所有点对之间的距离可以用换根 dp 在 \(O(n)\) 的时间复杂度内解决。
那么问题就转换成了不互质点对间的距离。
设现在的要解决的点为 \(rt\) ，我们以 \(rt\) 为根遍历整颗树。拿一个桶 \(d_i\) 表示所有点权包含 \(i\) 这个质因数的深度总和。然后对于 \(rt\) 我们不记录，dfs 完之后我们用 \(2^6\) 的时间容斥计算出所有与 \(rt\) 不互质的点到 \(rt\) 的距离。
这样我们做 \(n\) 遍，那么就出答案了。但是这样的复杂度是 \(O(n^2\times2^6)\)。
注意到题目中并没有给出固定的根，也就是这题没有一个会对答案造成影响的给出的根。那么我们套个点分治就好了。
总时间复杂度 \(O(n\log n\times2^6)\)。
代码如下：
#include<bits/stdc++.h>
#define ll long long
#define lowbit(i) (i&(-i))
using namespace std;
const int MAXN = 1e5+5;
const int MX = 1e5;
int n,a[MAXN],siz[MAXN];
ll ans,f[MAXN];
vector <int> e[MAXN],fac[MAXN];
void pre_dfs(int p,int fa)
{
siz[p]=1;f[p]=0;
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(to==fa) continue;
pre_dfs(to,p);
f[p]+=f[to]+siz[to];
siz[p]+=siz[to];
}
}
void dfs(int p,int fa)
{
ans+=f[p];
// cout<<p<<" "<<f[p]<<endl;
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(to==fa) continue;
f[to]=f[p]+1ll*siz[p]-2ll*siz[to];
siz[to]=siz[p];
dfs(to,p);
}
}
bool vis[MAXN];
int dp[MAXN],Tsiz,root,numb[MAXN][(1<<6)+5],cnt_1[(1<<6)+5],cnt;
ll d[MAXN],cnt_num[MAXN];
void Get_root(int p,int fa)
{
dp[p]=0;siz[p]=1;
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(to==fa||vis[to]) continue;
Get_root(to,p);
siz[p]+=siz[to];
dp[p]=max(dp[p],siz[to]);
}
dp[p]=max(dp[p],Tsiz-siz[p]);
if(dp[p]<dp[root]) root=p;
}
struct node
{
int p,dis;
}arr[MAXN];
void Get_dis(int p,int d,int fa)
{
arr[++cnt]=node{p,d};
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(to==fa||vis[to]) continue;
Get_dis(to,d+1,p);
}
}
void solve(int p)
{
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(vis[to]) continue;
cnt=0;Get_dis(to,1,p);
for(int j=1;j<=cnt;++j)
{
int now=arr[j].p,val=arr[j].dis;
for(int k=1;k<(1<<fac[now].size());++k)
{
int x=numb[now][k];
int cnt1=cnt_1[k];
if(cnt1&1) ans-=cnt_num[x]*val+d[x];
else ans+=cnt_num[x]*val+d[x];
}
}
for(int j=1;j<=cnt;++j)
{
int now=arr[j].p,val=arr[j].dis;
for(int k=1;k<(1<<fac[now].size());++k)
{
int x=numb[now][k];
d[x]+=val;
cnt_num[x]++;
}
}
}
for(int k=1;k<(1<<fac[p].size());++k)
{
int x=numb[p][k];
int cnt1=cnt_1[k];
if(cnt1&1) ans-=d[x];
else ans+=d[x];
}
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(vis[to]) continue;
cnt=0;Get_dis(to,1,p);
for(int j=1;j<=cnt;++j)
{
int now=arr[j].p,val=arr[j].dis;
for(int k=1;k<(1<<fac[now].size());++k)
{
int x=numb[now][k];
d[x]=0;
cnt_num[x]=0;
}
}
}
}
void Divide(int p)
{
vis[p]=1;
solve(p);
for(int i=0;i<e[p].size();++i)
{
int to=e[p][i];
if(vis[to]) continue;
root=0;Tsiz=siz[to];
Get_root(to,p);
Divide(root);
}
}
int lg[(1<<6)+5];
int main()
{
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=(1<<6);++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(int i=1;i<=n;++i)
{
int num=a[i];
int up=sqrt(num)+1;
for(int x=2;x<=up;++x)
{
if(num%x==0)
{
fac[i].push_back(x);
while(num%x==0) num/=x;
}
}
if(num!=1) fac[i].push_back(num);
numb[i][0]=1;
for(int j=1;j<(1<<fac[i].size());++j)
{
int k=lowbit(j);
numb[i][j]=numb[i][j-k]*fac[i][lg[k]-1];
}
}
for(int i=0;i<(1<<6);++i)
cnt_1[i]=__builtin_popcount(i);
for(int i=1;i<n;++i)
{
int u,v;
scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
pre_dfs(1,0);
dfs(1,0);
ans/=2;
dp[root=0]=n+1;Tsiz=n+1;
Get_root(1,0);
Divide(root);
printf("%lld\n",ans);
return 0;
}
简单的淀粉质。