Codeforces 809E. Surprise me! May 25, 2017 ###Description 给一棵树，每个点点权 $$a_i$$，保证 $$a_i$$各不相同，现在随机选两个点 $$u,v$$，求 $$f(u,v)=\phi(a_u\cdot a_v)\cdot dis(u,v)$$ 的期望，$$mod\ 10^9+7$$。 链接：[http://codeforces.com/contest/809/problem/E](http://codeforces.com/contest/809/problem/E "http://codeforces.com/contest/809/problem/E") ###Solution 首先，有一个结论：$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)},g=gcd(a,b)$$ 证明：考虑找一个 $$x$$，使得 $$x|b,gcd(\frac{b}{x},a)=1,gcd(x,\frac{b}{x})=1$$ 且 $$a$$ 包含 $$x$$ 中所有质因子。 那么 $$\phi(a\cdot b)=\phi(a)\cdot x\cdot\phi(\frac{b}{x})=\frac{\phi(a)\cdot\phi(b)\cdot x}{\phi(x)}$$ 显然，$$x$$ 是 $$g$$ 的倍数，所以 $$\frac{x}{g}=\frac{\phi(x)}{\phi(g)}$$，所以$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)}$$ 有了这个结论之后可以考虑点分，那么设 $$dis(x)$$ 表示 $$x$$ 到当前根的距离。 设 $$h(x)=\frac{x}{\phi(x)}$$，那么$$f(u,v)=\phi(a_u)\cdot\phi(a_v)\cdot h(g)\cdot(dis(u)+dis(v)),g=gcd(a_u,a_v)$$ 考虑当 $$u$$ 确定时，需要知道 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))$$ 和 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))\cdot dis(v)$$。 设 $$g(x)=h(x)-\sum[y|x,y\neq x]g(y)$$，那么 $$h(gcd(a_u,a_v))=\sum[x|a_u,x|a_v]g(x)$$ 这样就可以直接枚举约数算贡献了。 ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; inline void repr(int&a,int b){if(a<b)a=b;} #define mset(a,b) memset(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i) const int N=200007,P=1000000007; struct edge { int to;edge*ne; }_e[N*2],*e=_e,*p[N]; inline void add(int a,int b) { *e=(edge){b,p[a]};p[a]=e++; } std::vector<int>v[N]; int n,pr[N],pm,phi[N],inv[N],f[N],w[N],sz[N],rsz,nro,nsz,g[N],h[N],q[N],qe,ans; bool vis[N]; inline void dfs1(int x,int fa) { sz[x]=1; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { dfs1(i->to,x); sz[x]+=sz[i->to]; } } inline void dfs2(int x,int fa) { int t=rsz-sz[x]; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { repr(t,sz[i->to]); dfs2(i->to,x); } if(t<nsz)nsz=t,nro=x; } inline void set(int x,int y,int z) { if(!~g[x])q[qe++]=x,g[x]=h[x]=0; g[x]=(g[x]+(ll)y*f[x])%P; h[x]=(h[x]+(ll)z*f[x])%P; } inline void get(int x,int&y,int&z) { if(~g[x])y=g[x],z=h[x]; else y=z=0; } inline void dfs3(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P; foe(i,v[w[x]])set(*i,a,b); for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) dfs3(i->to,x,dis+1); } inline void dfs4(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P,A,B; foe(i,v[w[x]]) { get(*i,A,B); ans=(ans+(ll)a*B+(ll)b*A)%P; } for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) dfs4(i->to,x,dis+1); } inline void work(int x) { dfs1(x,0); rsz=nsz=sz[x],nro=x; dfs2(x,0); vis[x=nro]=1; foe(i,v[w[x]])set(*i,phi[w[x]],0); for(edge*i=p[x];i;i=i->ne) if(!vis[i->to]) { dfs4(i->to,x,1); dfs3(i->to,x,1); } fo0(i,qe)g[q[i]]=h[q[i]]=-1; qe=0; for(edge*i=p[x];i;i=i->ne) if(!vis[i->to])work(i->to); } int main() { fo1(i,N-1)for(int j=i;j<N;j+=i)v[j].push_back(i); fo(i,2,N-1) { if(!vis[i])pr[pm++]=i,phi[i]=i-1; for(int j=0;i*pr[j]<N;j++) { vis[i*pr[j]]=1; if(i%pr[j]==0) { phi[i*pr[j]]=phi[i]*pr[j]; break; } phi[i*pr[j]]=phi[i]*(pr[j]-1); } } phi[1]=1; inv[1]=1; fo(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P; fo1(i,N-1) { f[i]=(ll)i*inv[phi[i]]%P; foe(j,v[i])if(i^*j)(f[i]+=P-f[*j])%=P; } scanf("%d",&n); fo1(i,n)scanf("%d",w+i); fo0(i,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } mset(vis,0); mset(g,0xff); mset(h,0xff); work(1); ans=(ll)ans*inv[n]%P*inv[n-1]%P*2%P; printf("%d",ans); } ```
似乎虚树可以做到一个 log，感觉挺妙的。
https://blog.sengxian.com/solutions/cf-809e