AT_abc248_g [ABC248G] GCD cost on the tree

[problemUrl]: https://atcoder.jp/contests/abc248/tasks/abc248_g $ N $ 頂点からなる無向木が与えられます。 頂点を順に頂点 $ 1 $, 頂点 $ 2 $, $ \ldots $, 頂点 $ N $ とすると、 $ 1\leq\ i\leq\ N-1 $ について、$ i $ 番目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結んでいます。 また、それぞれの頂点には正整数が割り当てられており、 具体的には頂点 $ i $ には $ A_i $ が割り当てられています。 相異なる $ 2 $ 頂点 $ s $, $ t $ 間のコスト $ C(s,t) $ が次のようにして定められます。 > 頂点 $ s $ と頂点 $ t $ を結ぶ単純パス上の頂点を順に $ p_1(=s) $, $ p_2 $, $ \ldots $, $ p_k(=t) $ とする。 ここで、$ k $ はパス上の(端点含む)頂点数である。 > このとき、$ C(s,t)=k\times\ \gcd\ (A_{p_1},A_{p_2},\ldots,A_{p_k}) $ で定める。 > ただし、$ \gcd\ (X_1,X_2,\ldots,\ X_k) $ で $ X_1,X_2,\ldots,\ X_k $ の最大公約数を表す。 $ \displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N\ C(i,j) $ を $ 998244353 $ で割ったあまりを求めてください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\leq\ 10^5 $ - $ 1\leq\ U_i\