[CF1210C] Kamil and Making a Stream - map
Description
给定一棵n个点带点权的树,i号点的点定义f(i,j)为i到j路径上所有点的gcd,其中i是j的一个祖先,求所有f(i,j)之和
Solution
对于每个点,用一个 map
维护它到所有祖先的链上的 GCD 的每种可能值及个数,暴力递推即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, a[N];
vector<int> g[N];
map<int, int> f[N];
void dfs(int p, int from = 0)
{
f[p][a[p]]++;
for (int q : g[p])
{
if (q == from)
continue;
for (auto [x, y] : f[p])
{
int z = __gcd(x, a[q]);
f[q][z] += y;
}
dfs(q, p);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i < n; i++)
{
int p, q;
cin >> p >> q;
g[p].push_back(q);
g[q].push_back(p);
}
dfs(1);
int ans = 0;
for (int i = 1; i <= n; i++)
for (auto [x, y] : f[i])
ans += x * y, ans %= mod;
cout << ans << endl;
}