Kamil and Making a Stream

参考：Codeforces Round #588 (Div. 2)-E. Kamil and Making a Stream-求树上同一直径上两两节点之间gcd的和

思路：求的就是1~n之间所有最短路的gcd之和。

用一个set来储存每一个结点可能的gcd，另外再用一个三维的map来记录每一个结点的每一个gcd出现的次数。

代码：

// Created by CAD on 2019/9/28.

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+5;

vector<int> g[maxn];

map<ll,ll> cnt[maxn];

set<ll> s[maxn];

ll x[maxn];

ll ans=0;

const int mod=1e9+7;

void dfs(int u,int f)

{

    for(auto i:g[u])

    {

        if(i==f) continue;

        for(auto v:s[u])

        {

            ll temp=__gcd(1ll*v,x[i]);

            ans=(ans+1ll*temp%mod*cnt[u][v]%mod)%mod;

            cnt[i][temp]+=cnt[u][v];

            s[i].insert(temp);

        }

        s[i].insert(x[i]);

        ans=(ans+x[i]%mod)%mod;

        cnt[i][x[i]]++;

        dfs(i,u);

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n;

    cin>>n;

    for(int i=1;i<=n;++i)

        cin>>x[i];

    for(int i=1,u,v;i<=n-1;++i)

        cin>>u>>v,g[u].push_back(v),g[v].push_back(u);

    ans=(ans+x[1])%mod;

    s[1].insert(x[1]);

    cnt[1][x[1]]=1;

    dfs(1,-1);

    cout<<ans<<endl;

    return 0;

}

巴特西

Kamil and Making a Stream

最新文章

热门文章