ABC248G

· · 题解

考虑枚举 GCD 的值为 t，求出每个 t 对应的方案数 f_t。

直接求出有多少路径的 GCD 等于它不好求，我们考虑先求出满足 GCD 的值为 t 的倍数的方案数 g_t，则 f_t=g_t-\sum{f_{it}} (i>1)。

对于 g_t，我们先把所有满足 t \space | \space a_i 的 i 拉出来建出一个森林，在每一棵树上做树形 dp：

$len_i$ 表示 $i$ 的子树内，有一端点为 $i$ 的链的链长之和（准确的说应该是包括的点个数，没啥差别）。 $res_i$ 表示 $i$ 的子树内，经过 $i$ 的所有长度大于 $1$ 的链的长度之和。 那么 $g_t=\sum{res_i}$。 对于边 $(u,v)$，有转移： $res_u=res_u+cnt_u \times len_v + cnt_v \times len_u

前面的 res_u 是因为 v 子树内可以不选（但是 u 必须选），后面是计算两棵子树合并，子树根处两条链拼起来的总长度。

len_u=len_u+len_v+cnt_v $cnt_u=cnt_u+cnt_v

与 len_u 同理。

然后就做完了，时间复杂度 O(V \log V +n \sqrt V)。

#include<bits/stdc++.h>
using namespace std;
inline void dfs(int u,int tt){
    cnt[u]=1; len[u]=1; res[u]=0; col[u]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!col[v]) continue;
        dfs(v,tt);
        res[u]=(res[u]+(1ll*cnt[u]*len[v]%mod+1ll*cnt[v]*len[u]%mod)%mod)%mod;
        len[u]=(len[u]+len[v]+cnt[v])%mod;
        cnt[u]=cnt[u]+cnt[v];
    }
    (ans[tt]+=res[u])%=mod;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int x=read(); m=max(m,x);
        for(int j=1;j*j<=x;j++)
            if(x%j==0){
                g[j].emplace_back(i);
                if(j*j<x) g[x/j].emplace_back(i);
            }
    }
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v); add(v,u);
    }
    for(int i=m;i;i--){
        if(g[i].empty()) continue;
        for(int j=0;j<g[i].size();j++) col[g[i][j]]=1;
        for(int j=0;j<g[i].size();j++) if(col[g[i][j]]) dfs(g[i][j],i);
        for(int j=i+i;j<=m;j+=i) (ans[i]+=mod-ans[j])%=mod;
    }
    for(int i=1;i<=m;i++) (sum+=1ll*ans[i]*i%mod)%=mod;
    printf("%d\n",sum);
    return 0;
}