题意
有一棵 节点的树，根为 号节点。每个节点有两个权值 ，初始值均为 。
给出三种操作：
- 将 到根的路径上所有点的
- 将 到根的路径上所有点的
- 询问点 的权值
思路
如果单纯看的话需要维护的标记比较复杂，但是可以考虑使用矩阵乘法来描述。使用线段树维护矩阵和。对于操作 1，
对于操作 2
正确性可以得到保证（矩阵乘法满足结合律和对加法的分配律）
然后用线段树维护就很简单了。注意懒标记清空是清成单位矩阵。
xxxxxxxxxx
229
1
10
inline int read()
11
{
12
char c = getchar();
13
int s = 0;
14
bool x = 0;
15
while (!isdigit(c))
16
x = x | (c == '-'), c = getchar();
17
while (isdigit(c))
18
s = 10 * s + c - '0', c = getchar();
19
return x ? -s : s;
20
}
21
22
struct Matrix
23
{
24
int r, c;
25
int a[4][4];
26
void clear()
27
{
28
FOR(i, 1, r)
29
FOR(j, 1, c)
30
a[i][j] = 0;
31
}
32
Matrix() {}
33
Matrix(int _r ,int _c)
34
{
35
r = _r, c = _c;
36
clear();
37
}
38
void init(int _r ,int _c)
39
{
40
r = _r, c = _c;
41
clear();
42
}
43
} one;
44
45
Matrix operator*(const Matrix &a, const Matrix &b)
46
{
47
int r = a.r, c = b.c, p = a.c;
48
Matrix ret(r, c);
49
FOR(i, 1, r)
50
FOR(j, 1, c)
51
FOR(k, 1, p)
52
ret.a[i][j] += a.a[i][k] * b.a[k][j];
53
return ret;
54
}
55
56
Matrix operator+(const Matrix &a, const Matrix &b)
57
{
58
int r = a.r, c = a.c;
59
Matrix ret(r, c);
60
FOR(i, 1, r)
61
FOR(j, 1, c)
62
ret.a[i][j] = a.a[i][j] + b.a[i][j];
63
return ret;
64
}
65
66
const int maxn = 1e6 + 5;
67
int head[maxn], to[maxn << 1], nxt[maxn << 1], cntedge;
68
int n, m;
69
int fa[maxn], dep[maxn], son[maxn], size[maxn], dfn[maxn], top[maxn], cnt;
70
71
struct Segment
72
{
73
Matrix val;
74
Matrix tag;
75
bool marked;
76
} f[maxn << 2];
77
78
void pushup(int i, int j, int k)
79
{
80
f[k].val = f[L].val + f[R].val;
81
return;
82
}
83
84
void pushdown(int i, int j, int k)
85
{
86
f[L].val = f[L].val * f[k].tag;
87
f[R].val = f[R].val * f[k].tag;
88
f[L].tag = f[L].tag * f[k].tag;
89
f[R].tag = f[R].tag * f[k].tag;
90
f[L].marked |= 1, f[R].marked |= 1;
91
f[k].marked = 0;
92
f[k].tag = one;
93
return;
94
}
95
96
void build(int i, int j, int k)
97
{
98
f[k].tag = one;
99
f[k].val.init(1, 3);
100
f[k].val.a[1][3] = 1;
101
if (i == j)
102
return;
103
build(i, M, L);
104
build(M + 1, j, R);
105
return;
106
}
107
108
int query(int i, int j, int k, int x)
109
{
110
if (i == j)
111
return f[k].val.a[1][2];
112
if (f[k].marked)
113
pushdown(i, j, k);
114
if (x <= M)
115
return query(i, M, L, x);
116
else return query(M + 1, j, R, x);
117
}
118
119
void modify(int i, int j, int k, int x, int y, int d, int opt)
120
{
121
if (x <= i && y >= j)
122
{
123
Matrix A = one;
124
if (opt == 1)
125
A.a[3][1] = d;
126
else
127
A.a[1][2] = d;
128
f[k].tag = f[k].tag * A;
129
f[k].marked = 1;
130
f[k].val = f[k].val * A;
131
return;
132
}
133
if (f[k].marked)
134
pushdown(i, j, k);
135
if (x <= M)
136
modify(i, M, L, x, y, d, opt);
137
if (y > M)
138
modify(M + 1, j, R, x, y, d, opt);
139
pushup(i, j, k);
140
return;
141
}
142
143
il int query(int x)
144
{
145
return query(1, n, 1, dfn[x]);
146
}
147
148
void modify(int x, int d, int opt)
149
{
150
while (top[x] != 1)
151
{
152
modify(1, n, 1, dfn[top[x]], dfn[x], d, opt);
153
x = fa[top[x]];
154
}
155
modify(1, n, 1, 1, dfn[x], d, opt);
156
return;
157
}
158
159
void add(int u, int v)
160
{
161
to[++cntedge] = v;
162
nxt[cntedge] = head[u];
163
head[u] = cntedge;
164
return;
165
}
166
167
void dfs1(int u, int father, int depth)
168
{
169
size[u] = 1;
170
dep[u] = depth;
171
fa[u] = father;
172
int maxson = -1;
173
for (int i = head[u]; i; i = nxt[i])
174
{
175
int v = to[i];
176
if (v == father)
177
continue;
178
dfs1(v, u, depth + 1);
179
size[u] += size[v];
180
if (size[v] > maxson)
181
maxson = size[v], son[u] = v;
182
}
183
return;
184
}
185
186
void dfs2(int u, int topf)
187
{
188
dfn[u] = ++cnt;
189
top[u] = topf;
190
if (!son[u])
191
return;
192
dfs2(son[u], topf);
193
for (int i = head[u]; i; i = nxt[i])
194
{
195
int v = to[i];
196
if (v == fa[u] || v == son[u])
197
continue;
198
dfs2(v, v);
199
}
200
return;
201
}
202
203
int main()
204
{
205
one.init(3, 3);
206
FOR(i, 1, 3)
207
one.a[i][i] = 1;
208
n = read();
209
reg int u, v, opt, x;
210
FOR(i, 1, n - 1)
211
{
212
u = read(), v = read();
213
add(u, v);
214
add(v, u);
215
}
216
dfs1(1, 0, 1);
217
dfs2(1, 1);
218
build(1, n, 1);
219
m = read();
220
FOR(i, 1, m)
221
{
222
opt = read(), x = read();
223
if (opt < 3)
224
modify(x, read(), opt);
225
else if (opt == 3)
226
printf("%d\n", query(x));
227
}
228
return 0;
229
}
留言