/category/df/ /archives/236/ 2017-05-25T20:24:07+08:00 ###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 typedef long long ll; inline void repr(int&a,int b){if(ato,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(tne) 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 /archives/96/ 2016-12-05T13:02:00+08:00 ###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 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 inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template 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]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