【*2000 暴力树形DP】CF1230 E

深藏阁楼爱情的钟 2024-03-17 18:39 102阅读 0赞

[Problem - E - Codeforces][]

题意：

![25adb30bd05a42c1b4173f8e1deb9f20.png][]

思路：

![29ad24147a454bfc8a1b91a72bdcc7ef.png][]

![8b32e926cec446a3b83b383faa82235e.png][]

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxv=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    map<int,int> mp[mxv];
    
    int N,u,v;
    int tot=0,ans=0;
    int a[mxn];
    int head[mxn];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        for(auto p:mp[fa]){
            ans+=p.second*(__gcd(p.first,a[u]))%mod;
            ans%=mod;
            mp[u][__gcd(p.first,a[u])]+=p.second;
        }
        ans+=a[u];
        ans%=mod;
        mp[u][a[u]]++;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N;i++) cin>>a[i];
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        cout<<ans%mod<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1230/problem/E
[25adb30bd05a42c1b4173f8e1deb9f20.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6bbe6139dea04fba9900ac8d044bdd72.png
[29ad24147a454bfc8a1b91a72bdcc7ef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/bd0ea246c547499f91592e45a5bcb9a3.png
[8b32e926cec446a3b83b383faa82235e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d5663d9b04b649d1ba5aa8a1b10b97bc.png