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); } ```
BZOJ 3697: 采药人的路径 December 5, 2016 ###Description 采药人的药田是一个树状结构，每条路径上都种植着同种药材。 采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。 采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。 ###Input 第1行包含一个整数N。 接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。 ###Output 输出符合采药人要求的路径数目。 ###Sample Input 7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1 ###Sample Output 1 ###HINT 对于100%的数据，N ≤ 100,000。 ###Solution 点分治，边权为0变成-1，dfs时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2]; ll ans; bool vis[100001]; struct edge { int to,ne,w; }e[200000]; inline void add(int a,int b,int w) { e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++; } void dfs1(int x,int fa) { sz[x]=1; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs1(e[i].to,x),sz[x]+=sz[e[i].to]; } void dfs2(int x,int fa) { bool ok=sz[ro]<=2*sz[x]; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) { dfs2(e[i].to,x); if(sz[e[i].to]*2>sz[ro])ok=0; } if(ok)nro=x; } void dfs3(int x,int fa,int len) { if(len) { if(apr[len+n]) ans+=cnt[n-len][0]; else ans+=cnt[n-len][1]; } else { if(apr[len+n]) ans+=cnt[n][0]+1; else ans+=cnt[n][0]; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs3(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs4(int x,int fa,int len) { if(len) { if(apr[len+n]) cnt[n+len][0]++,cnt[n+len][1]++; else cnt[n+len][0]++; } else { cnt[n][0]++; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs4(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs5(int x,int fa,int len) { cnt[n+len][0]=cnt[n+len][1]=0; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs5(e[i].to,x,len+e[i].w); } void solve(int x) { dfs1(x,0); ro=x; dfs2(x,0); vis[nro]=1; for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w); dfs5(nro,0,0); for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])solve(e[i].to); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c?c:-1),add(b,a,c?c:-1); } solve(1); printf("%lld\n",ans); } ```