这题正解是虚树，本解法卡常，仅适合不会虚树的。(例如本人)
注意：下文中根节点深度定义为 1 .
第一步: 转化问题
我们把 $ g(x,y,z) $ 拆开，考虑每个质数是哪些点的因子。
包含这个质数的点构成一个点集，我们只需求这个点集 S 的 $ \sum\limits_{x,y,z\in S } f(x,y,z) $。
第二步: 对于已知点集 S 的 $ \sum\limits_{x,y,z\in S } f(x,y,z) $
首先考虑三个点构成的最小连通块的边数。
这可以简单计算出：
\[\dfrac{\operatorname{dist}(u,v)+\operatorname{dist}(v,w)+\operatorname{dist}(u,w)}{2} \]通过式子可以算出，点集内每两个点的距离恰好被计算 $ \frac{|S|-2}{2} $ 次。
通过某种方法计算 $\sum\limits_{x,y\in S } \operatorname{dist}(x,y) $ ，乘上 $ \frac{|S|-2}{2} $ 获得答案。
第三步: "某种方法"
我们需要求：
\[\sum\limits_{x,y\in S } \operatorname{dist}(x,y) \]使用树上差分：
\[\operatorname{dist}(x,y) = \operatorname{depth}(x) + \operatorname{depth}(y) - 2 \operatorname{depth}(\operatorname{lca}(u,v)) \]带回求和得到
\[ \begin{aligned} \sum\limits_{x,y\in S } \operatorname{dist}(x,y) = \sum\limits_{x,y\in S } \operatorname{depth}(x) + \operatorname{depth}(y) - 2 \operatorname{depth}(\operatorname{lca}(u,v))\\ \end{aligned} \]我们依次加入点，通过记录前面的点的深度和以及前面的点的个数，可以简单处理这个式子的前两块。
对于包含 LCA 的深度的部分，我们通过数据结构可以处理。
加入一个点的时候，给这个点到根节点的所有点点权加上一，查询一个点的时候，查询这个点到根节点的点权和，这就是这个点与之前所有点的 LCA 的深度和。
为什么呢？
考虑 LCA 的深度在树上的实际意义，就是两点到根的路径的重合点数，然后就好理解了。
代码
本题卡常，代码中使用了树状数组而不是线段树。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
const int MxN=200000;
int n,Answer,result,TotalDepth,Count;
int head[MxN+5],nxt[2*MxN+5],to[2*MxN+5],tot;
int siz[MxN+5],depth[MxN+6],son[MxN+5],top[MxN+5],father[MxN+5];
int L[MxN+5],R[MxN+5],rnk[MxN+5],tim;
int value[MxN+5];
vector<int>Ver[MxN+5];
int Pow(int A,int B){
int res=1;
while(B){
if(B&1){
res=res*A%MOD;
}
A=A*A%MOD;
B>>=1;
}
return res;
}
void AddEdge(int u,int v){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
void DFS1(int p,int fa){
siz[p]=1;
father[p]=fa;
depth[p]=depth[fa]+1;
for(int i=head[p];i;i=nxt[i]){
if(to[i]!=fa){
DFS1(to[i],p);
siz[p]+=siz[to[i]];
if(siz[to[i]]>siz[son[p]]){
son[p]=to[i];
}
}
}
}
void DFS2(int p,int fa,int tp){
L[p]=++tim;
rnk[tim]=p;
top[p]=tp;
if(son[p]){
DFS2(son[p],p,tp);
}
for(int i=head[p];i;i=nxt[i]){
if(to[i]!=fa&&to[i]!=son[p]){
DFS2(to[i],p,to[i]);
}
}
R[p]=tim;
}
struct BIT{
int T[MxN+5],TT[MxN+5];
void Modify(int l,int r,int c){
for(int i=l;i<=n;i+=i&-i){T[i]+=c;TT[i]+=c*l;}
for(int i=(r+1);i<=n;i+=i&-i){T[i]-=c;TT[i]-=c*(r+1);}
}
int Query(int l,int r){
int res=0;
for(int i=r;i;i-=i&-i){res+=(r+1)*T[i];res-=TT[i];}
for(int i=l-1;i;i-=i&-i){res-=(l)*T[i];res+=TT[i];}
return res;
}
}bit;
void Insert(int u){
int res=TotalDepth+Count*depth[u],v=u;
while(v){
res=(res-2*bit.Query(L[top[v]],L[v])%MOD+MOD)%MOD;
bit.Modify(L[top[v]],L[v],1);
v=father[top[v]];
}
TotalDepth=(TotalDepth+depth[u])%MOD;
Count=(Count+1)%MOD;
result=(result+res)%MOD;
}
void Delete(int u){
int v=u;
while(v){
bit.Modify(L[top[v]],L[v],-1);
v=father[top[v]];
}
}
void Calculate(int num){
result=0;TotalDepth=0;Count=0;
for(auto i:Ver[num]){
Insert(i);
}
Answer=(Answer+result*(Count-2)%MOD*Pow(2,MOD-2)%MOD)%MOD;
for(auto i:Ver[num]){
Delete(i);
}
}
signed main(){
int u,v;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&value[i]);
int t=value[i];
for(int j=2;j*j<=t;j++){
if(t%j==0){
Ver[j].push_back(i);
while(t%j==0){
t/=j;
}
}
}
if(t>1){
Ver[t].push_back(i);
}
}
for(int i=1;i<n;i++){
scanf("%lld%lld",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
DFS1(1,0);
DFS2(1,0,1);
for(int i=2;i<=MxN;i++){
Calculate(i);
}
printf("%lld\n",Answer);
}
总结
使用了很顺畅的思路流程，不是正解而且卡常，但是好理解才是重要的。
标签：CF1972E,int,题解,sum,operatorname,MxN,depth,dist,Divisors From： https://www.cnblogs.com/WangManhe/p/17752002.html