CF1101D 题解

传送门

题目大意

给出一棵(n)个节点的树,每个节点上有点权(a_i)
求最长的树上路径,满足条件:路径上经过节点(包括两个端点)点权的(gcd)和不等于1。

(Solution:)

因为这是DP专题里的题目,我们往(DP)的方向想
可以看出这道题很像点分治,这启发我们像点分治一样合并两条路径
对于一个顶点(u)(此处默认(u)为路径上深度最浅的点),令(f_{u,j})表示从(i)向下挂出的路径上的点权均能被(j)整除的最大路径长度,那么对于(u)的一个子节点(v),有
(f_{u,j}=maxlimits_{d_{u,j}=d_{v,k}}(f_{u,j},f_{v,k}+1)),其中(d_{u,j},d_{v,k})分别为(a_u,a_v)的第(j,k)个质因子
更新答案时,(ans=max(ans,f_{u,j}+f_{v,k})),意思即为合并(u,v)往下挂出的两条路径(注意这句话要写在(f)数组更新之前)
最后若(ans=0),则需要特判(具体见代码)
时间复杂度(O(n sqrt n ))(并不能过gdfzoj上的加强版数据)
UPD:此题在优化后过了(10^6)的数据,具体优化见代码

原来未优化的部分代码

inline void euler()
{
	int cnt=0;
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i<=maxn;i++)
	{
        if(isprime[i]) prime[++cnt]=i;
        fr(j,1,cnt)
		{
            if(i*prime[j]>maxn) break;
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
    isprime[0]=isprime[1]=false;
    return ;
}
inline void getsingle()
{
	fr(i,1,n) fr(j,1,sqrt(a[i]))
	{
		if(a[i]%j!=0) continue;
		if(isprime[j])	d[i][++id[i]]=j,f[i][id[i]]=1;
		if(isprime[a[i]/j]&&j*j!=a[i]) d[i][++id[i]]=a[i]/j,f[i][id[i]]=1;
	}
	return ;
}

优化后的代码

#include<bits/stdc++.h>
using namespace std;
namespace my_std
{
	typedef long long ll;
	typedef double db;
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register int i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register int i=(x);i>=(y);i--)
	#define enter pc('
')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	const int inf=0x3f3f3f3f;
	const ll inff=1e15;
	inline int read()
	{
		int sum=0,f=1;
		char ch=0;
		while(!isdigit(ch))
		{
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			sum=(sum<<1)+(sum<<3)+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	inline void writeln(int x)
	{
		write(x);
		enter;
	}
	inline void writesp(int x)
	{
		write(x);
		space;
	}
}
using namespace my_std;
const int N=1e6+50;
int n,cnt,maxn=-inf,ans,primecnt,a[N],head[N],prime[N],id[N],d[N][15],f[N][15];
bool isprime[N];
struct edge
{
	int nxt,to;
}e[N<<1];
inline void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
inline void euler()
{
	int cnt=0;
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i<=maxn;i++)
	{
        if(isprime[i]) prime[++cnt]=i;
        fr(j,1,cnt)
		{
            if(i*prime[j]>maxn) break;
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
    isprime[0]=isprime[1]=false;
    primecnt=cnt;
    return ;
}
inline void getsingle()
{
    //这里由枚举a[i]的因数改变成枚举质数再判断整除
    fr(i,1,n) fr(j,1,100)
    {
	if(prime[j]>a[i]) break;//注意这里不能是sqrt(a[i]),因为大于sqrt(a[i])的质数可能是由小于sqrt(a[i])的一个合数除a[i]得来的,调了1h
	if(a[i]%prime[j]!=0) continue;
	d[i][++id[i]]=prime[j],f[i][id[i]]=1;
	//if(isprime[a[i]/prime[j]]&&prime[j]*prime[j]!=a[i]) d[i][++id[i]]=a[i]/prime[j],f[i][id[i]]=1;
    }
    return ;
}
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		if(id[u]&&id[v]) fr(j,1,id[u]) fr(k,1,id[v])
		{
			if(d[u][j]!=d[v][k]) continue;
			ans=max(ans,f[u][j]+f[v][k]);
			f[u][j]=max(f[u][j],f[v][k]+1);
		}
	}
	return ;
}
int main(void)
{
	n=read();
	fr(i,1,n) a[i]=read(),maxn=max(a[i],maxn);
	fr(i,1,n-1)
	{
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	bool husu=1;
	fr(i,1,n) if(a[i]!=1) husu=0;
	if(husu)
	{
		puts("0");
		return 0;
	}
	euler();
	getsingle();
	dfs(1,1);
	if(ans) writeln(ans);
	else puts("1");
	return 0;
}
/*
    ^ ^   ^ ^
   (OwO) (OwO)
~(- - -) (- - -)~
  / /   / /
*/

完结撒花!!!

原文地址:https://www.cnblogs.com/lgj-lgj/p/12613020.html