思路
这E题有点暴力
由于不同的gcd(u, v)的个数不会超过(log_2V)，V是树上最大的数，所以每个结点开个数组，保存从根节点到该节点的所有gcd值。暴力搞就好了。
#include <bits/stdc++.h>
using namespace std;
#define endl '
'
typedef long long ll;
const int N = 1e5 + 10;
const int M = 1e9 + 7;
map<int, map<ll, int>> ds;
ll val[N];
vector<int> np[N];
ll ans = 0;
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a%b);
}
void dfs(int p, int fa) {
ds[p][val[p]] = 1;
if(p != 1)
for(auto par : ds[fa]) {
ll g = gcd(par.first, val[p]);
ans = (ans + g * par.second) % M;
if(ds[p].count(g)) ds[p][g] += par.second;
else ds[p][g] = par.second;
}
ans = (ans + val[p]) % M;
for(int nt : np[p]) {
if(nt == fa) continue;
dfs(nt, p);
}
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> val[i];
}
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
np[u].push_back(v);
np[v].push_back(u);
}
dfs(1, 0);
cout << ans << endl;
}