Codeforces 990G 点分治+暴力

题意：给出一棵点带权的树，求i$\in$[1,200000]所有路径的上点权的gcd==i的个数。

考虑点分治，对于一棵以u为根的子树，如何统计经过u的路径的答案？

显然既然是经过点u的路径，那么所有经过u的路径上的点权的gcd肯定是点u的点权的约数。

暴力算下，2e5以内最多只有160个约数。

然后dfs出u子树里所有点到u路径的gcd，然后用个桶，最多$u的点权的约数个数^2$数下数就行了，但是实际应该是远远不满的。

最慢的一个点1404ms，4.5s的时限应该没什么问题。

然而这题的标签里有个dp(滑稽

//by zykykyk

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<iostream>

using namespace std;

#define ll long long

#define For(i,x,y) for (register int i=(x);i<=(y);i++)

#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)

#define cross(i,k) for (register int i=first[k];i;i=last[i])

inline ll read(){

    ll x=0;int ch=getchar(),f=1;

    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();

    if (ch=='-'){f=-1;ch=getchar();}

    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

const int N = 2e5+10;

int n,x,y,Size,rt,a[N];

ll ans[N];

int tot,first[N],last[N<<1],to[N<<1];

inline void Add(int x,int y){to[++tot]=y,last[tot]=first[x],first[x]=tot;}

int size[N],Max[N];

bool vis[N];

inline void GetRoot(int u,int fa){

	Max[u]=0,size[u]=1;

	cross(i,u) if (to[i]!=fa&&!vis[to[i]]) GetRoot(to[i],u),size[u]+=size[to[i]],Max[u]=max(Max[u],size[to[i]]);

	Max[u]=max(Max[u],Size-size[u]);

	if (Max[rt]>Max[u]) rt=u;

}

int cnt,g[N];

ll b[N];

inline int gcd(int a,int b){return !b?a:gcd(b,a%b);}

inline void dfs(int u,int fa,int Gcd,int x,int rt){

	if (x!=1||x==1&&u!=rt) g[++cnt]=Gcd,b[Gcd]++;

	cross(i,u) if (to[i]!=fa&&!vis[to[i]]) dfs(to[i],u,gcd(Gcd,a[to[i]]),x,rt);

}

inline void solve(int u){

	cnt=0,dfs(u,u,a[u],1,u),vis[u]=1;

	sort(g+1,g+1+cnt);

	int tot=unique(g+1,g+1+cnt)-g-1;

	For(i,1,tot){

		ans[g[i]]+=b[g[i]]+b[g[i]]*(b[g[i]]-1)/2;

		For(j,i+1,tot) ans[gcd(g[i],g[j])]+=b[g[i]]*b[g[j]];

	}

	For(i,1,tot) b[g[i]]=0;

	cross(k,u)

		if (!vis[to[k]]){

			cnt=0,dfs(to[k],u,gcd(a[u],a[to[k]]),0,to[k]);

			sort(g+1,g+1+cnt);

			int tot=unique(g+1,g+1+cnt)-g-1;

			For(i,1,tot){

				ans[g[i]]-=b[g[i]]*(b[g[i]]-1)/2;

				For(j,i+1,tot) ans[gcd(g[i],g[j])]-=b[g[i]]*b[g[j]];

			}

			For(i,1,tot) b[g[i]]=0;

		}

	cross(i,u) if (!vis[to[i]]) Size=size[to[i]],rt=0,GetRoot(to[i],u),solve(rt);

}

int main(){

	n=read();

	For(i,1,n) a[i]=read(),ans[a[i]]++;

	For(i,1,n-1) x=read(),y=read(),Add(x,y),Add(y,x);

	Size=n,Max[0]=1e9,GetRoot(1,1),solve(rt);

	For(i,1,N-10) if (ans[i]) printf("%d %lld\n",i,ans[i]);

}

巴特西

Codeforces 990G 点分治+暴力

最新文章

热门文章