OI相关：

A：

分为两种情况处理：$u$ 到 $lca$ 和 $lca$ 到 $v$。

我的做法是先树剖， 将每条链单独拿出来拉出来，根据 $a_i$ 和 $b_i$ 连边，正反各建一棵树，维护一下 $k$ 级祖先。

然后从 $u$ 到 $v$ 的时候每次根据从 dfs 序由小到大还是由大到小选择上面说的正树或是反树，二分找到合适的出口，转移即可。

时间复杂度 $\mathcal O((n+q)\log^2 n)$。

我是什么傻逼才想出来码量这么大还麻烦的做法，糖丸了。

B：

式子有点长，不想写了

C：

考虑把求距离和矩阵乘法两部分合到一起做。

以 1 为根，设 $G_{x}$ 表示 $x$ 子树中的所有点到 $x$ 的矩阵之和，也就是

$$G_{x}=\sum_{y \in son_x} \operatorname{arr}^{A \times(\operatorname{dis}(x，y)+1)}(k-1)^{A \times n-A \times(\operatorname{dis}(x, y)+1)}$$

那么所有的 $s=x$ 且 $t \in x$ 的子树的贡献 我们就一并统计了，此时 $G_{1}$ 就是 $s=1$ 的答案， $G_{x}$ 的转移式也很好写出：

$G_{x}=\left(\sum_{y \in s o n_{x}} G_{y}+I \times(k-1)^{A \times n}\right) \times \operatorname{arr}^{A} \times\left(\frac{1}{k-1}\right)^{A} 。$

类似的，其它点的贡献可以用换根 dp 求出，适当的预处理一下矩阵和 $k$ 的快速幂可以做到 $O\left(2^{3} n\right)$ 。

---

🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽🐽

今天抽了半周年池子。

大号还差一个拉🐕，本来70抽三个六星该出了， 结果后面两个都歪了，分别造出了四潜的焰影苇草和三潜的斥罪，不过又快保底了，看我妈手气罢。

值得一提的是我给我大号和k8的b服号抽的时候都是单点一个四星接送的十连第一个出忍冬。

然后是我小号（我妈的号），上号发现一个月没看，号上多了一百多石头+2w合成玉，简单抽了八十抽毕业了，有一个双黄俩忍冬/kk。

虽然还没出拉🐕，但是大号80六星所以纪念一下。

今天ez放假。

为什么我考完试就放假啊为什么我考完试就放假啊为什么我考完试就放假啊为什么我考完试就放假啊为什么我考完试就放假啊为什么我考完试就放假啊为什么我考完试就放假啊

想回家和同学van。

恼了，不过习惯了。