题目描述

有一棵$n$节点的树,根为$1$号节点。每个节点有两个权值$k_i, t_i$,初始值均为$0$

给出三种操作:

  1. $\mathrm{Add}( x , d )$操作:将$x$到根的路径上所有点的$k_i\leftarrow k_i + d$
  2. $\mathrm{Mul}( x , d )$操作:将$x$到根的路径上所有点的$t_i\leftarrow t_i + d \times k_i$
  3. $\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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int head[N], rest[2 * N], to[2 * N], tot;

inline void add(int u, int v) { to[++ tot] = v, rest[tot] = head[u], head[u] = tot; }

struct Mat {
ll x[3];
inline Mat() { memset(x, 0, sizeof x); }
inline Mat operator * (Mat b) {
Mat c;
c.x[0] = x[0] + b.x[0],
c.x[1] = x[1] + b.x[1],
c.x[2] = x[0] * b.x[1] + x[2] + b.x[2];
return c;
}
} mat[N * 10], op1, op2;

int fa[N], top[N], pos[N], cnt, sz[N], son[N];

inline void dfs(int u) {
sz[u] = 1;
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(v == fa[u]) continue;
fa[v] = u, dfs(v), sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}

inline void dfs(int u, int tp) {
top[u] = tp, pos[u] = ++ cnt;
if(son[u]) dfs(son[u], tp);
for(int i = head[u] ; i ; i = rest[i]) {
int v = to[i];
if(v == fa[u] || v == son[u]) continue;
dfs(v, v);
}
}

#define lc (id << 1)
#define rc (id << 1 | 1)

inline void push(int id) {
if(mat[id].x[0] || mat[id].x[1] || mat[id].x[2])
mat[lc] = mat[lc] * mat[id],
mat[rc] = mat[rc] * mat[id],
memset(mat[id].x, 0, 3 * sizeof(ll));
}

inline void modify(int id, int l, int r, int ql, int qr, Mat &mt) {
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) {
mat[id] = mat[id] * mt;
return ;
}
push(id);
if(ql <= mid) modify(lc, l, mid, ql, qr, mt);
if(qr > mid) modify(rc, mid + 1, r, ql, qr, mt);
}

inline void query(int &pos) {
for(int id = 1, l = 1, r = cnt, mid ; l <= r ; (push(id), pos <= mid) ? (r = mid, id = lc) : (l = mid + 1, id = rc)) {
if(l == r) { printf("%lld\n", mat[id].x[2]); return ; }
mid = (l + r) >> 1;
}
}

int n, m;

template<typename T> inline void read(T &x) {
char c = x = 0; bool f = 0;
while(!isdigit(c))
f |= (c = getchar()) == '-';
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
if(f) x = -x;
}

int main() {
read(n);
for(int i = 1, u, v ; i < n ; ++ i)
read(u), read(v), add(u, v), add(v, u);
dfs(1), dfs(1, 1);
read(m);
for(int i = 1, op, x, y ; i <= m ; ++ i) {
read(op), read(x);
if(op == 1)
for(read(op1.x[0]) ; x ; x = fa[top[x]])
modify(1, 1, cnt, pos[top[x]], pos[x], op1);
else if(op == 2)
for(read(op2.x[1]) ; x ; x = fa[top[x]])
modify(1, 1, cnt, pos[top[x]], pos[x], op2);
else query(pos[x]);
}
}