[ABC248G] GCD cost on the tree

Problem Statement

You are given an undirected tree with $N$ vertices.
Let us call the vertices Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$. For each $1\leq i\leq N-1$, the $i$-th edge connects Vertex $U_i$ and Vertex $V_i$.
Additionally, each vertex is assigned a positive integer: Vertex $i$ is assigned $A_i$.

The cost between two distinct vertices $s$ and $t$, $C(s,t)$, is defined as follows.

Let $p_1(=s)$, $p_2$, $\ldots$, $p_k(=t)$ be the vertices of the simple path connecting Vertex $s$ and Vertex $t$, where $k$ is the number of vertices in the path (including the endpoints).
Then, let $C(s,t)=k\times \gcd (A_{p_1},A_{p_2},\ldots,A_{p_k})$,
where $\gcd (X_1,X_2,\ldots, X_k)$ denotes the greatest common divisor of $X_1,X_2,\ldots, X_k$.

Find $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$, modulo $998244353$.

Constraints

$2 \leq N \leq 10^5$
$1 \leq A_i\leq 10^5$
$1\leq U_i<V_i\leq N$
All values in input are integers.
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

Output

Print $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$, modulo $998244353$.

Sample Input 1

Sample Output 1

There are edges directly connecting Vertex $1$ and $2$, Vertex $1$ and $3$, and Vertex $3$ and $4$.
Thus, the costs are computed as follows.

$C(1,2)=2\times \gcd(24,30)=12$
$C(1,3)=2\times \gcd(24,28)=8$
$C(1,4)=3\times \gcd(24,28,7)=3$
$C(2,3)=3\times \gcd(30,24,28)=6$
$C(2,4)=4\times \gcd(30,24,28,7)=4$
$C(3,4)=2\times \gcd(28,7)=14$

Thus, the sought value is $\displaystyle\sum_{i=1}^{3}\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47$ modulo $998244353$, which is $47$.

Sample Input 2

10
180 168 120 144 192 200 198 160 156 150
1 2
2 3
2 4
2 5
5 6
4 7
7 8
7 9
9 10

Sample Output 2

两个东西乘起来，很不好算。我们尝试拆开来算，就是枚举一个，求另一个的和。

路径数量和 gcd，看起来枚举gcd更容易。为了方便，设一个边 $(u,v)$ 的边权为 $\gcd(a_u,a_v)$，这样也好加边。设现在枚举，令 $k$ 为枚举到的最小公因数，一个很自然的想法就是把所有 $a$ 为 $k$ 的倍数的边拎出来，组成一棵树，然后跑一个 dp。考虑一条边 $(u,v,w)$，那么 $w$ 的因数个数就是他会被计算的次数，因数个数 $\sqrt{w}$ 个，所以如果能保证dp和建树是严格 $O(n)$，最终复杂度是 $O(n\sqrt{n})$

先来看一下怎么dp。现在给出一棵树，我们要求所有路径长度之和。首先可以每个连通块单独考虑。定义 $dp_i$ 为所有树上以 $i$ 为端点的路径之和， $c_i$ 为 $i$ 为根的子树大小。那么 $dp_v$ 转移到 $dp_i$ 时，共有 $c_v$ 个路径，他们长度全部增加1。算最终答案时，目前的 $dp_i$ 会有多 $c_v$ 个， $dp_v$ 会多目前的 $c_i$ 个。

但是我们发现这样算出来的答案不完全对。因为我们并不能保证这些路径的 $\gcd$ 为 $k$，只能保证他是 $k$ 的倍数。我们可以用筛法处理出一个容斥系数。因为我在算 $k$ 的答案一定算了 $2k$ 的答案，在 $2k$ 时容斥系数要减去那么多。

总复杂度 $O(n\sqrt{n)$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=998244353;
int n,a[N],u[N],vis[N],e_num,hd[N],ret,ans,c[N],dp[N],p[N],fp[N],v[N];
struct edge{
	int v,nxt;
}e[N<<1];
vector<int>g[N],f[N];
void add_edge(int u,int v)
{
	e[++e_num]=(edge){v,hd[u]};
	hd[u]=e_num;
}
int gcd(int x,int y)
{
	if(!y)
		return x;
	return gcd(y,x%y);
}
void dfs(int x,int y)
{
//	printf("%d %d\n",x,y);
	vis[x]=0;
	dp[x]=c[x]=1;
	fp[x]=0;
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].v==y)
			continue;
		dfs(e[i].v,x);
		int ac=c[x],ad=dp[x];
		int bc=c[e[i].v],bd=dp[e[i].v];
		(fp[x]+=(1LL*ad*bc%P+1LL*ac*bd%P)%P)%=P;
		(fp[x]+=fp[e[i].v])%=P;
		(dp[x]+=(bc+bd)%P)%=P; 
		(c[x]+=bc)%=P;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=1;i<N;i++)
		for(int j=1;j*i<N;j++)
			g[i*j].push_back(i);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",u+i,v+i);
		int w=gcd(a[u[i]],a[v[i]]);
		for(int j=0;j<g[w].size();j++)
			f[g[w][j]].push_back(i);
	}
	for(int i=1;i<N;i++)
	{
		p[i]+=i;
	    for(int j=2;1LL*j*i<N;j++)
        	p[j*i]-=p[i];
        e_num=0;
        for(int j=0;j<f[i].size();j++)
        {
        	int x=u[f[i][j]],y=v[f[i][j]];
        	add_edge(x,y);
        	add_edge(y,x);
        	vis[x]=vis[y]=1;
		}
		for(int j=0;j<f[i].size();j++)
        {
        	int x=u[f[i][j]];
        	if(vis[x])
        	{
        		dfs(x,0);
        		(ans+=(1LL*fp[x]%P*p[i]%P))%=P;
        	}
		}
		for(int j=0;j<f[i].size();j++)
        {
        	int x=u[f[i][j]],y=v[f[i][j]];
        	hd[x]=hd[y]=0;
		}
//		for(int i=1;i<=n;i++)
//			printf("%d ",fp[i]);
//		putchar('\n');
    }
    printf("%d",ans);
}

原文链接: https://www.cnblogs.com/mekoszc/p/17020433.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/309291

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！