Dasha Code Championship - SPb Finals Round(C. Kamil and Making a Stream)(树上gcd的传递)

传送门 最关键的性质是一个节点的值往下传递，最多只会改变$log1e12$次，约等于40. 这表明向下搜索的过程中，传递到每个节点的不同值的个数不会超过40。

#include<bits/stdc++.h> using namespace std; #define fore(i, l, r) for(int i = int(l); i < int(r); i++) #define MAXN 100005 #define ll long long int n; ll a[MAXN]; vector<int>e[MAXN]; inline bool read() { scanf("%d", &n); fore(i,0,n)scanf("%lld",a+i); fore(i,0,n-1) { int a,b;scanf("%d%d",&a,&b);a--;b--; e[a].push_back(b);e[b].push_back(a); } } ll ans=0; const ll mod=1000000007; void dfs(int x,int pre,unordered_map<ll,int>res) { res[a[x]]++; unordered_map<ll,int>now; for (auto add:res) { ll g=__gcd(add.first,a[x]); now[g] += add.second; ans+=g*add.second; } ans%=mod; for (auto it:e[x]) { if (it == pre)continue; dfs(it,x,now); } } inline void solve() { unordered_map<ll,int>mp; dfs(0,-1,mp); cout<<ans<<endl; } int main() { #ifdef _DEBUG freopen("input.txt", "r", stdin); #endif read(); solve(); return 0; }