本文共 1591 字，大约阅读时间需要 5 分钟。

题意：

n个点的无向无权树，根是第1个节点。每个点有一个权值  。

 表示  节点和  节点之间路径上的点的  。

让你计算  ，其中  是  的祖先。答案会取模。

数据范围： 。

题解：

这道题我能想到的只有俩做法。

（1）以每个节点为路径上最靠近根节点的点去计算。即  。

（2）以每个节点为路径上最远离根节点的点去计算。即  。

但是这俩复杂度是一个能过一个不能过。

我认为的复杂度是这样的。但我并不会严格证明。

（1） 

你会发现当你遍历到  节点时，该节点存储的gcd个数并不会很多。

稍微想一想发现，当前节点存储的gcd需要满足倍数关系。

设当前节点存储的gcd集合是T。那么  ，认为  是常数， 是倍数。

就是一个节点存储的gcd，它不能同时有2和3，因为这俩不是倍数关系。

（2）

我们知道一个数  约数个数的上限是  。

举一个过不去的例子。

假如当前节点有  个儿子节点，并且这些节点都是叶子节点，且这些节点的值都是当前节点的两两不同的约数。

那么当前节点就存储了  个gcd。

如果当前节点到根节点有  个节点，并且这些节点的值都等于当前节点的值。

那么这  个gcd都需要转移  次。肯定过不去。

感受：

我写过的cf题从不卡常，我竟然去尝试卡常，而没有选择去想一想复杂度对不对。

多想一想吧。

代码：

#include<bits/stdc++.h>using namespace std ;typedef long long ll ;const int maxn = 1e5 + 5 ;const ll mod = 1e9 + 7 ;map<ll , int> cnt[maxn] ;int n ;ll x[maxn] ;int num , head[maxn] ;ll ans = 0 ;ll gcd(ll a , ll b){return b ? gcd(b , a % b) : a ;}struct Edge{   int v , next ;	} edge[maxn << 1] ;void add_edge(int u , int v){	edge[num].v = v ;	edge[num].next = head[u] ;	head[u] = num ++ ;}void dfs(int f , int u){	cnt[u][x[u]] ++ ;	for(auto y : cnt[u])       ans += y.first * cnt[u][y.first] , ans %= mod ;			for(int i = head[u] ; i != -1 ; i = edge[i].next)    {    	int v = edge[i].v ;    	if(v == f)  continue ;    	for(auto y : cnt[u])    	{    		ll nxt = gcd(x[v] , y.first) ;    	    cnt[v][nxt] += cnt[u][y.first] ;			}    	dfs(u , v) ;	}	  }int main(){	scanf("%d" , &n) ;	for(int i = 1 ; i <= n ; i ++)  scanf("%lld" , &x[i]) ;	num = 0 , memset(head , -1 , sizeof(head)) ;	for(int i = 1 ; i <= n - 1 ; i ++)	{		int u , v ;		scanf("%d%d" , &u , &v) ;		add_edge(u , v) ;		add_edge(v , u) ;	}	dfs(0 , 1) ;	printf("%lld\n" , ans) ;	return 0 ;}