Description：

给定两棵 $n$ 个节点的树 $T1,T2$ ，求： $$ \sum_{i=1}^n\sum_{j=i+1}^ndis_1(i,j)\times dis_2(i,j)\mod998244353 $$ $1\leqslant n\leqslant 10^5$

Solution：

第一种做法：对 $T1$ 边分治，然后两边黑白染色拿到 $T2$ 上建虚树 $DP$ 算贡献。

第二种做法：

先化式子： $$ \begin{align} &\sum_{i=1}^n\sum_{j=i+1}^ndis_1(i,j)\times dis_2(i,j)\\ =&\frac 1 2\sum_{i=1}^n\sum_{j=1}^ndis_1(i,j)\times(dep_2[i]+dep_2[j])-\sum_{i=1}^n\sum_{j=1}^ndis_1(i,j)\times dep_2[LCA_2(i,j)])\\ =&\sum_{i=1}^n\sum_{j=1}^ndis_1(i,j)\times dep_2[i]-\sum_{i=1}^n\sum_{j=1}^ndis_1(i,j)\times dep_2[LCA_2(i,j)]) \end{align} $$ 于是我们可以 $dfs$ 枚举 $LCA_2(i,j)$ ，然后对 $T_1$ 边分树合并，就可以计算答案了。

Code：