注意到只要考虑祖先和后代之间的贡献
发现对于一个节点，他和所有祖先最多产生 $log$ 个不同的 $gcd$
所以每个节点开一个 $vector$ 维护祖先到自己所有不同的 $gcd$ 和这个 $gcd$ 的出现次数即可
之所以可以用 $vector$ 而不用 $set$ 是因为每个节点越祖先的节点下来的 $gcd$ 显然是越小的，存在单调性
直接根据单调性从父亲的 $vector$ 小到大和自己的值 $gcd$ 并加入到自己的 $vector$ 里面，父亲的都加完后最后加入本身的值到 $vector$ 最后面即可
因为每个节点最多有 $log$ 个不同的 $gcd$ ，所以复杂度是对的
总复杂度 $O(n log (10^{12}))$
当然用 $set$ 多一个 $log$ 应该也能过
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,mo=1e9+7; int n; ll val[N]; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } struct dat { ll d,cnt; dat (ll _d=0,ll _cnt=0) { d=_d,cnt=_cnt; } }; vector <dat> V[N]; inline ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; } void dfs(int x,int fa) { if(fa) for(auto A: V[fa]) { ll d=gcd(A.d,val[x]); if(V[x].empty() || V[x].back().d!=d) V[x].push_back(dat(d,A.cnt)); else V[x].back().cnt+=A.cnt; } if(V[x].empty() || V[x].back().d!=val[x]) V[x].push_back(dat(val[x],1)); else V[x].back().cnt++; for(int i=fir[x];i;i=from[i]) if(to[i]!=fa) dfs(to[i],x); } int main() { n=read(); for(int i=1;i<=n;i++) val[i]=read(); int a,b; for(int i=1;i<n;i++) { a=read(),b=read(); add(a,b); add(b,a); } dfs(1,0); ll Ans=0; for(int i=1;i<=n;i++) for(auto A: V[i]) Ans=(Ans+A.d*A.cnt)%mo; printf("%lld ",Ans); return 0; }