记录一下第一个自己做出来的矩阵乘法数据结构题
传送门
大意是给你一个树，每个点维护两个权值k[i]，t[i]，初始为0
支持如下操作：
1、Add(x,d) 将x到根的路径上的点k[i]+=d
2、Mul(x,d) 将x到根的路径上的点t[i]+=d*k[i]
3、询问t[x]

首先非常显然的，使用树链剖分可以一个log的代价把原问题转化为区间问题
然后考虑维护一个节点的信息，由于操作2每个点加的值不同，一个显然的想法是构造一个矩阵，利用矩阵乘法
一个节点上我们记录

\[\begin{bmatrix} k_i \\ t_i \end{bmatrix} \]

容易发现维护操作2的方法

\[\begin{bmatrix} 1 & 0 \\ d & 1 \end{bmatrix} \begin{bmatrix} k_i \\ t_i \end{bmatrix} = \begin{bmatrix} k_i \\ t_i + d*k_i \end{bmatrix} \]

但是这样操作一处理较为麻烦
这里有一个常用技巧，就是把矩阵中引入一个1
一个节点上我们记录

\[\begin{bmatrix} k_i \\ t_i \\ 1 \end{bmatrix} \]

对于操作1

\[\begin{bmatrix} 1 & 0 & d \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} k_i \\ t_i \\ 1 \end{bmatrix} = \begin{bmatrix} k_i + d \\ t_i \\ 1 \end{bmatrix} \]

对于操作2

\[\begin{bmatrix} 1 & 0 & 0 \\ d & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} k_i \\ t_i \\ 1 \end{bmatrix} = \begin{bmatrix} k_i \\ t_i + d * k_i \\ 1 \end{bmatrix} \]

代码在路上了鸽了