link
第一步，莫比乌斯反演：
\[\begin{aligned}
s(T)=&\sum _{e\in T}w_e\\
&\sum _{T}s(T) \gcd \{w_e\mid e\in T\}\\
=&\sum_{T}s(T) \sum _{d | w_e, e\in T}\varphi(d)\\
=&\sum _{d=1}^{V}\varphi(d) \sum _{T}s(T)[\forall e \in T,d|w_e]
\end{aligned}
\]
枚举每个 \(d\)，求边权为 \(d\) 的整数倍的所有生成树权值和。
根据矩阵树定理，
\[\sum_{T \subseteq \mathcal T(G)}\prod _{e\in T}w_e =\det L(G)_{[n]\setminus \{k\},[n]\setminus \{k\}}
\]
然后就是你要求和，改一下 \(w_e\) 就好了，可以用多项式的方法，把它改成 \(w_ex+1\)，这样子乘起来的一次项就是你的答案。