题目描述
有一棵$n$节点的树，根为$1$号节点。每个节点有两个权值$k_i, t_i$，初始值均为$0$
给出三种操作：
- $\mathrm{Add}( x , d )$操作：将$x$到根的路径上所有点的$k_i\leftarrow k_i + d$
- $\mathrm{Mul}( x , d )$操作：将$x$到根的路径上所有点的$t_i\leftarrow t_i + d \times k_i$
- $\mathrm{Query}( x )$操作：询问点$x$的权值$t_x$
题解
发现前两个操作实际上是一个多变量的线性变换，不妨用矩阵维护
先树链剖分，将树上问题转化为序列上的问题
对于每个位置，相当于一个三元组：$\begin{pmatrix}k & t & 1 \end{pmatrix}$
对于操作一，转移为
$$
\begin{pmatrix}k & t & 1 \end{pmatrix}
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
d & 0 & 1
\end{pmatrix}
=
\begin{pmatrix}k+d & t & 1 \end{pmatrix}
$$
对于操作二，转移为
$$
\begin{pmatrix}k & t & 1 \end{pmatrix}
\begin{pmatrix}
1 & d & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
=
\begin{pmatrix}k & t+d \times k & 1 \end{pmatrix}
$$
之后就是区间乘矩阵、查询单点矩阵值的线段树板子题了
但要直接这么做时间复杂度为$O(27n \log^2 n)$，跑得十分慢
不如分析一下矩阵的构造，找一下哪些点是会改变
首先第三列的值是不会变的，因为这是给最后的$1$提供贡献
其次主对角线的$1$是不会变的，因为线性转移后各自位都有本身的单位贡献
同时第二行第一列的$0$也不会变，因为$t$不会对$k$产生贡献
那么也就是说矩阵转移实际上是这个
$$
\begin{pmatrix}
1 & x_2 & 0 \\
0 & 1 & 0 \\
x_1 & x_3 & 1
\end{pmatrix}
$$
也就是说只需要维护三个值即可，那么转移呢？
$$
\begin{pmatrix}
1 & x_2 & 0 \\
0 & 1 & 0 \\
x_1 & x_3 & 1
\end{pmatrix}
\begin{pmatrix}
1 & y_2 & 0 \\
0 & 1 & 0 \\
y_1 & y_3 & 1
\end{pmatrix}
=
\begin{pmatrix}
1 & x_2+y_2 & 0 \\
0 & 1 & 0 \\
x_1+y_1 & x_1y_2+x_3+y_3 & 1
\end{pmatrix}
$$
于是时间复杂度降到了$O(3n \log^2 n)$
代码
1 |
|
