1 solutions

  • 1
    @ 2021-9-5 10:46:03

    大家都知道 φ(n)=npnp1p \varphi(n)=n\prod_{p|n}\frac {p-1} p 吧。

    以及,d2nμ(nd2) \sum_{d^2|n}\mu(\frac n {d^2}) 实际上是刘维尔函数。刘维尔函数就是 λ(n)=(1)Ω(n) \lambda(n)=(-1)^{\Omega(n)} ,其中 Ω(n) \Omega(n) n n 的质因子个数(可重)。

    可以知道 λ \lambda 完全积性 的。

    于是原柿就可以这样化简:

    i=1nj=i+1ndis(i,j)×λ(dis(i,j))pdis(i,j)p1p\prod_{i=1}^n\prod_{j=i+1}^ndis(i,j) \times \lambda(dis(i,j))\prod_{p|dis(i,j)}\frac {p-1} p

    前半部分计算每一个 a a 对答案的贡献,我们来讨论后半部分。

    i=1nj=i+1npdis(i,j)p1p\prod_{i=1}^n\prod_{j=i+1}^n\prod_{p|dis(i,j)}\frac {p-1} p

    pi=1nj=i+1n(p1p)[pdis(i,j)]\prod_p\prod_{i=1}^n\prod_{j=i+1}^n(\frac {p-1} p)^{[p|dis(i,j)]}

    p(p1p)i=1nj=i+1n[pdis(i,j)]\prod_p(\frac {p-1} p)^{\sum_{i=1}^n\sum_{j=i+1}^n[p|dis(i,j)]}

    于是我们可以枚举 p p ,然后统计有多少条路径中有 p p ,复杂度 O(n2V) O(n^2V)

    再想想,我们可以使用树形 DP 来统计这东西,复杂度 O(nV) O(nV)

    但实际上出现的质数最有 O(5n) O(5n) ,所以实际上复杂度是 O(5n2) O(5n^2) 的。

    我们在树上标记 pau p|a_u 的所有节点 u u ,容易发现这些节点将树分成了若干个连通块(被标记的节点单独算一个连通块),两两之间都会对答案产生贡献。

    假设有 cnt cnt 个连通块,连通块的大小分别为 B1,B2,...Bcnt B_1,B_2,...B_{cnt}

    那么路径条数就是:

    i=1cntj=i+1cntBi×Bj\sum_{i=1}^{cnt}\sum_{j=i+1}^{cnt}B_i \times B_j

    稍微转化一下可以得到答案是:

    (i=1cntBi)2i=1cntBi22\frac {(\sum_{i=1}^{cnt}B_i)^2-\sum_{i=1}^{cnt}B_i^2} 2

    也就是

    n2i=1cntBi22\frac {n^2-\sum_{i=1}^{cnt}B_i^2} 2

    只需要找到每个连通块大小的平方即可。

    继续优化,发现可以使用树形 DP \rm DP 来优化这玩意儿,于是就只需要树上被标记过的节点,可以使用虚树优化。在分解质因子的时候优化一下,复杂度 O(V+7nlogn) O(V+7n\log n)

    不过其实可以省掉虚树的排序,在 DFS 时分解质因子即可。

    std:

    #include<cstdio>
    #include<vector>
    typedef unsigned uint;
    typedef unsigned long long ull;
    const uint M=1e5+5,V=1e6+5,mod=998244353,MOD=998244352;
    uint n,mx,ans=1,a[M];std::vector<uint>id[78499],G[M];
    uint dfc,f[M],d[M],son[M],siz[M],top[M];ull s2[M];
    uint fs[M],fa[M],siz1[M];ull siz2[M];bool vis[M];
    uint tp,tot,q[M],stk[M];uint Tp,del[M];
    uint Top,pri[78499],pos[V];
    inline uint pow(uint a,uint b){
    	uint ans=1;
    	for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;
    	return ans;
    }
    inline void sieve(const uint&n){
    	register uint i,j,x;
    	for(i=2;i<=n;++i){
    		if(!pos[i])pri[++Top]=i,pos[i]=Top;
    		for(j=1;j<=Top&&(x=i*pri[j])<=n;++j)if((pos[x]=pos[i])==j)break;
    	}
    }
    void DFS1(const uint&u){
    	uint x=a[u],y;bool tag=false;siz[u]=1;d[u]=d[f[u]]+1;
    	while(x^1){
    		id[pos[x]].push_back(u);y=pri[pos[x]];
    		while(!(x%y))x=1.*x/y,tag=!tag;
    	}
    	for(uint&v:G[u]){
    		if(v==f[u])continue;
    		f[v]=u;DFS1(v);siz[u]+=siz[v];s2[u]+=1ull*siz[v]*siz[v];
    		if(siz[v]>siz[son[u]])son[u]=v;
    	}
    	ans=1ull*ans*pow(tag?mod-a[u]:a[u],(1ull*n*n-s2[u]-1ull*(n-siz[u])*(n-siz[u])-1>>1)%MOD)%mod;
    }
    void DFS2(const uint&u,const uint&tp){
    	top[u]=tp;
    	if(!son[u])return;DFS2(son[u],tp);
    	for(uint&v:G[u]){
    		if(v==f[u]||v==son[u])continue;
    		DFS2(v,v);
    	}
    }
    inline uint LCA(uint u,uint v){
    	while(top[u]^top[v]){
    		if(d[top[u]]>d[top[v]])u=f[top[u]];
    		else v=f[top[v]];
    	}
    	return d[u]>d[v]?v:u;
    }
    inline uint Find(uint u,uint v){
    	while(top[u]^top[v]){
    		if(f[top[u]]==v)return top[u];
    		u=f[top[u]];
    	}
    	return son[v];
    }
    inline void Insert(const uint&u){
    	if(!tp)return void(stk[tp=1]=u);
    	uint v=LCA(u,stk[tp]);
    	while(tp>1&&d[v]<d[stk[tp-1]])G[stk[tp-1]].push_back(stk[tp]),--tp;
    	if(d[v]<d[stk[tp]])G[v].push_back(stk[tp--]);
    	if(!tp||stk[tp]!=v)stk[++tp]=v;
    	if(stk[tp]!=u)stk[++tp]=u;
    }
    inline void Build(){
    	tp=0;if(q[1]!=1)stk[tp=1]=1;
    	for(register uint i=1;i<=tot;++i)Insert(q[i]),vis[q[i]]=true;
    	while(tp>1)G[stk[tp-1]].push_back(stk[tp]),--tp;
    }
    ull Query(const uint&u){
    	ull S=0,ans=0;
    	for(uint&v:G[u]){
    		fs[v]=Find(v,u);fa[v]=u;ans+=Query(v);S+=1ull*siz[fs[v]]*siz[fs[v]];
    		if(vis[u]&&vis[v])ans+=1ull*(siz[fs[v]]-siz[v])*(siz[fs[v]]-siz[v]);
    		if(vis[v]){
    			siz1[u]+=siz[fs[v]];siz2[u]+=1ull*siz[fs[v]]*siz[fs[v]];
    		}
    		else{
    			siz1[u]+=siz1[v];siz2[u]+=siz2[v];
    		}
    	}
    	if(!vis[u]){
    		if(vis[fa[u]])ans+=1ull*(siz[fs[u]]-siz1[u])*(siz[fs[u]]-siz1[u]);
    		if(!fa[u])ans+=1ull*(n-siz1[u])*(n-siz1[u]);
    	}
    	else ans+=s2[u]-S+1;
    	del[++Tp]=u;
    	return ans;
    }
    signed main(){
    	register uint i,u,v;ull n2;
    	scanf("%d",&n);n2=1ull*n*n;
    	for(i=1;i<n;++i){
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);G[v].push_back(u);
    	}
    	for(i=1;i<=n;++i)scanf("%u",a+i),mx=a[i]>mx?a[i]:mx;sieve(mx);
    	DFS1(1);DFS2(1,1);
    	for(i=1;i<=n;++i)G[i].clear();
    	for(i=1;i<=Top;++i){
    		if(id[i].empty())continue;
    		for(uint&u:id[i])q[++tot]=u;Build();tot=0;
    		ans=1ull*ans*pow(1ull*(pri[i]-1)*pow(pri[i],mod-2)%mod,(n2-Query(1)>>1)%MOD)%mod;
    		while(Tp){
    			fs[del[Tp]]=fa[del[Tp]]=siz1[del[Tp]]=siz2[del[Tp]]=0;
    			G[del[Tp]].clear();vis[del[Tp]]=false;
    			--Tp;
    		}
    	}
    	printf("%u",ans);
    }
    
    • 1

    Information

    ID
    195
    Time
    500ms
    Memory
    128MiB
    Difficulty
    9
    Tags
    # Submissions
    32
    Accepted
    4
    Uploaded By