mcfx's blog - 点分治

mcfx's blog - 点分治 2017-05-25T20:24:07+08:00 Typecho /feed/atom/category/df/ <![CDATA[Codeforces 809E. Surprise me!]]> /archives/236/ 2017-05-25T20:24:07+08:00 2017-05-25T20:24:07+08:00 admin

###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);
}
```

]]> <![CDATA[BZOJ 3697: 采药人的路径]]> /archives/96/ 2016-12-05T13:02:00+08:00 2016-12-05T13:02:00+08:00 admin

###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);
}
```

]]>