本文于 github 博客同步更新。
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)\) 。
标签：总结,为什么,2024.11,times,right,考完试,operatorname,放假 From： https://www.cnblogs.com/Mitishirube0717/p/18521021