CF809E Surprise me!

套路题

求：

$\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i\times a_j)·dist(i,j)$

有一说一感觉这题非常套路。。~~模版练习题~~

然后看了看其他题解感觉 dp 部分可以不用做得那么麻烦吧（）

首先显然我们不管前面那个分数。然后发现式子里面有 $\varphi(a_i\times a_j)$ 这个不太好处理的东西。。思考一下，我们希望能够化成这样的形式：

$\sum_{i=1}^n \sum_{j=1}^n A_i A_j dist(i,j)$

这个东西看起来就比较好树形 dp 求出来。于是考虑把 $\varphi(a_ia_j)$ 拆成 $\varphi(a_i)\varphi(a_j)$ 这个东西。我们考虑对于一个质数 $p_k$ ，如果有 $p_k | a_i$ 那么这个在算 $\varphi(a_i)$ 的时候就会乘上 $(p_k-1)p_k^{\alpha - 1}$ 次方。如果它不存在于 $a_j$ 中，那么它对 $\varphi(a_ia_j)$ 的贡献仍然是 $(p_k-1)p_k^{\alpha - 1}$ ，没有区别。否则，假设它对 $a_j$ 贡献是 $(p_k-1)p_k^{\beta-1}$ ，那么它对 $\varphi(a_ia_j)$ 相比于 $\varphi(a_i)\varphi(a_j)$ 就少贡献了 $\frac{p_k}{p_k-1}$。形式化地说：

$\varphi(a_ia_j) = \varphi(a_i)\varphi(a_j) \prod_{p_k|\gcd(a_i,a_j)} \frac{p_{k}}{p_k-1}$

这里就有了一个结论

$\varphi(ab) = \frac{\varphi(a)\varphi(b)d}{\varphi(d)} ,d = \gcd(a,b)$

我们设 $t(x) = \prod_{p_k|x} \frac{p_{k}}{p_k-1}$ ，也就是说要做的是

$\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j) t(\gcd(a_i,a_j)) dis(i,j)\\\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j)dis(i,j) \sum_{k=1}^n [\gcd(a_i,a_j)=k] t(k)\\$

把 $k$ 提到前面去，那么就是：

$\sum_{k=1}^nt(k)\sum_{k|a_i}\sum_{k|a_j} [\gcd(\frac {a_i}k ,\frac{a_j} k) = 1] \varphi(a_i)\varphi(a_j) dis(i,j)\\$

于是我们设 $F(k)$ 为所有 $\gcd(a_i,a_j)=k$ 的 $(i,j)$ 的答案。算出这个再乘上 $t(k)$ 就是最后的答案了。

$F(k) = \sum_{k|a_i} \sum_{k|a_j} [\gcd(\frac{a_i} k,\frac{a_j} k) = 1]\varphi(a_i)\varphi(a_j) dis(i,j)\\$

莫反一下：

$F(k) = \sum_{k|a_i} \sum_{k|a_j} \varphi(a_i)\varphi(a_j) dis(i,j) \sum_{kd|\gcd(a_i,a_j)} \mu(d)$

把 $d$ 放到前面枚举：

$F(k) = \sum_{d=1}^n \mu(d) \sum_{kd|a_i} \sum_{kd|a_j} \varphi(a_i) \varphi(a_j) dis(i,j)$

然后经典换 $T$ ：

$F(k) = \sum_{k|T} \mu(\frac T k)\sum_{T|a_i}\sum_{T|a_j} \varphi(a_i)\varphi(a_j)dis(i,j)$

后面那个式子看起来比较好求，我们单独设 $f(k) = \sum_{k|a_i} \sum_{k|a_j} \varphi(a_i)\varphi(a_j) d(i,j)$ ，然后 $F$ 的式子就变成了：

$F(k) = \sum_{k|T} \mu(\frac T k) f(k)$

我们考虑 $f$ 怎么求，我们枚举 $k$ 并且枚举点权为 $k$ 的倍数的点，拖出来建棵虚树，然后问题就变成了：

$\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j)dis(i,j)$

这个就是前面说的那个看起来很可做的东西。。我们 dfs 一次求出到 1 的 $\sum_{j=1}^n \varphi(a_j)dis(i,j)$ 然后再 dfs 的过程中维护这个值就好了。具体就是把这个值减去子树的权值和，再加上这个子树外的权值和（因为外面的点 $dis$ 增加了一，里面的点 $dis$ 减少了1）。

求出 $f$ ，于是就做完了。最坏复杂度大概是 $O(n d(n)\log(n))$ ？反正 CF 8s 很稳。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007
typedef long long ll;
int n , m;
int A[MAXN];

int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}

int pri[MAXN] , en , phi[MAXN] , mu[MAXN] , poi[MAXN];
void sieve() {
    phi[1] = mu[1] = 1;
    for( int i = 2 ; i < MAXN ; ++ i ) {
        if( !pri[i] ) pri[++ en] = i , phi[i] = i - 1 , mu[i] = -1;
        for( int j = 1 ; j <= en && i * pri[j] < MAXN ; ++ j ) {
            pri[i * pri[j]] = 1;
            if( i % pri[j] == 0 ) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
            phi[i * pri[j]] = phi[i] * ( pri[j] - 1 ) , mu[i * pri[j]] = -mu[i];
        }
    }
}

vector<int> G[MAXN];
int g[MAXN][19] , dep[MAXN] , dfn[MAXN] , R[MAXN] , bac[MAXN] , clo;
void dfs( int u , int fa ) {
    dfn[u] = ++ clo , bac[clo] = u;
    for( int v : G[u] ) if( v != fa ) {
            dep[v] = dep[u] + 1;
            g[v][0] = u;
            rep( k , 1 , 18 ) if( g[g[v][k-1]][k-1] ) g[v][k] = g[g[v][k-1]][k-1]; else break;
            dfs( v , u );
        }
    R[u] = clo;
}
int lca( int u , int v ) {
    if( dep[u] < dep[v] ) swap( u , v );
    if( dep[u] != dep[v] )
        per( k , 18 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
    if( u == v ) return u;
    per( k , 18 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
    return g[u][0];
}

vector<int> p;

namespace faketree { // build faketree with nodes from p
    bool cmp(int a, int b) { return dfn[a] < dfn[b]; }
    vector<int> G[MAXN];
    int n;
    int stk[MAXN] , tp , rt;
    void build() {
        sort(all(p) , cmp);
        rep(i, 1, p.size() - 1) p.pb(lca(p[i], p[i - 1]));
        sort(all(p) , cmp);
        n = unique( all( p ) ) - p.begin();
        tp = 0;
        stk[0] = 0;
        rt = p[0];
        rep( i , 0 , n - 1 ) {
            while( tp && R[stk[tp]] < dfn[p[i]] ) -- tp; // cur chain (in stack) is already added
            G[stk[tp]].pb( p[i] ) , G[p[i]].pb( stk[tp] );
            stk[++ tp] = p[i];
        }
    }
    int cur , sz[MAXN] , re , vis[MAXN];
    void dfs1( int u , int fa ) {
        sz[u] = vis[u] * phi[A[u]] , ( cur += ( vis[u] * 1ll * ( dep[u] - dep[rt] ) * phi[A[u]] ) % P ) %= P;
        for( int v : G[u] ) if( v != fa ) {
                dfs1( v , u );
                ( sz[u] += sz[v] ) %= P;
            }
    }
    void dfs( int u , int fa ) {
        ( re += ( 1ll * vis[u] * cur * phi[A[u]] ) % P ) %= P;
        for( int v : G[u] ) if( v != fa ) {
                int del =  1ll * ( dep[v] - dep[u] ) * ( ( 1ll * sz[rt] - 2 * sz[v] ) % P + P ) % P;
                if( !u ) del = 0;
                ( cur += del ) %= P;
                dfs( v , u );
                ( cur += P - del ) %= P;
            }
    }
    int workit( ) {
        for( int x : p ) vis[x] = 1;
        build( );
        re = cur = 0; dep[0] = -1;
        dfs1( 0 , 0 );
        dfs( 0 , 0 );
        for( int x : p ) G[x].clear() , vis[x] = 0; G[0].clear();
        return re;
    }
}

vi fk[MAXN];
int f[MAXN];

void solve() {
    sieve();
    cin >> n;
    rep( i , 1 , n ) scanf("%d",&A[i]) , fk[A[i]].pb( i );
    int u , v;
    rep( i , 2 , n ) scanf("%d%d",&u,&v) , G[u].pb( v ) , G[v].pb( u );
    dep[1] = 1; dfs( 1 , 1 );
    rep( i , 1 , n ) {
        p.clear();
        for (int j = i; j <= n; j += i)
            for (int t : fk[j]) p.pb(t);
        f[i] = faketree::workit();
    }
//    rep( i , 1 , n ) printf("%d ",f[i]); puts("");
    rep( i , 1 , n )
        for( int j = i + i ; j <= n ; j += i ) ( f[i] += f[j] * mu[j / i] < 0 ? f[j] * mu[j / i] + P : f[j] * mu[j / i] ) %= P; // now f is F
//    rep( i , 1 , n ) printf("%d ",f[i]); puts("");
    rep( i , 1 , n ) poi[i] = 1;
    rep( i , 1 , en ) if( pri[i] <= n )
            for( int j = pri[i] ; j <= n ; j += pri[i] ) poi[j] = 1ll * poi[j] * Pow( pri[i] - 1 , P - 2 ) % P , poi[j] = 1ll * poi[j] * pri[i] % P;
    int ans = 0;
    rep( i , 1 , n )
        ( ans += 1ll * poi[i] * f[i] % P ) %= P;
    printf("%lld\n",1ll * ans * Pow( 1ll * n * ( n - 1 ) % P , P - 2 ) % P);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}