CF1230E Kamil and Making a Stream

题意

给出一颗树，求所有节点到其各个祖先路径上所有点的$gcd$值之和

数据范围：$1 \le n \le 100000,0 \le x_i \le 10^{12}$

题解

发现节点的值达到$10^{12}$，肯定不能一个个求$gcd$
父节点维护的值是可以传给子节点用的，所以可以在$dfs$时记录，但是空间够吗？
注意到$gcd$值如果改变，至少$/2$，也就是说一个节点维护的$gcd$最多只有$\log_210^{12}(<40)$种取值，而且我们不关心每种值的来源（即产生它的路径），只关心有哪些值以及它们的个数，因此足以为每一个节点开一个$map$记录

代码：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef long long LL;
typedef map<LL,int>::iterator it;
const int N=100000+10;
const int mod=1e9+7;
map<LL,int> s[N];
int n,u,v;
LL a[N];
int cnt;
int head[N];
LL ans;
struct edge{
    int nxt,to;
} e[N<<1];
inline void add(int u,int v){
    e[++cnt]=(edge){head[u],v};
    head[u]=cnt;
}
LL gcd(LL a,LL b){
    return b?gcd(b,a%b):a;
}
void dfs(int u,int f){
    for(it i=s[u].begin();i!=s[u].end();i++)
        (ans+=(*i).first*(*i).second)%=mod;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f)
            continue;
        s[v][a[v]]=1;
        for(it j=s[u].begin();j!=s[u].end();j++)
            s[v][gcd((*j).first,a[v])]+=(*j).second;
        dfs(v,u);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    s[1][a[1]]=1;
    dfs(1,0);
    printf("%lld",ans);
    return 0;
}