首先，树剖无疑。
其次，不会了...
搜了发题解才知道咋写。
没有什么正(wo)常(hui)点(xie)的线段树直接做的写法。
换个形式，发现题目中的修改可以用矩阵乘法来表示
一个节点用一个$1 \times 3$的矩阵来表示
$$
\begin{bmatrix}
1 & v & t
\end{bmatrix}
$$
然后修改一的矩阵为
$$
\begin{bmatrix}
1 & d & 0 \\\\
0 & 1 & 0 \\\\
0 & 0 & 1
\end{bmatrix}
$$
节点矩阵右乘修改一矩阵就可以得到修改之后的矩阵
$$
\begin{bmatrix}
1 & v & t
\end{bmatrix} \times
\begin{bmatrix}
1 & d & 0 \\\\
0 & 1 & 0 \\\\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
1 & d + v & t
\end{bmatrix}
$$
修改二矩阵为
$$
\begin{bmatrix}
1 & 0 & 0 \\\\
0 & 1 & d \\\\
0 & 0 & 1
\end{bmatrix}
$$
$$
\begin{bmatrix}
1 & v & t
\end{bmatrix}
\times
\begin{bmatrix}
1 & 0 & 0 \\\\
0 & 1 & d \\\\
0 & 0 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & v & t + d\times v
\end{bmatrix}
$$
然后用线段树维护矩阵乘法即可，因为答案要求的是叶子节点的$t$，所以一直pushdown标记即可，不用pushup操作。
然后矩阵乘法本来是$O(n^3)$的，但是因为这个矩阵左下角三个元素一直为$0$，那么可以直接把式子展开，直接赋值，优化掉这个$n^3=27$的常数。
能用矩阵乘法也太秀了吧。
#include <bits/stdc++.h> #define ll long long using namespace std; template<typename T> inline void read(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); } while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - 48; ch = getchar(); } x *= f; } const int N = 1e5 + 7; struct Matrix { ll m[3][3]; Matrix() { memset(m, 0, sizeof m); } void init() { for (int i = 0; i < 3; i++) m[i][i] = 1; } bool empty() { return !m[0][1] && !m[0][2] && !m[1][2]; } void clear() { m[0][1] = m[0][2] = m[1][2] = 0; } }; Matrix operator * (const Matrix &a, const Matrix &b) { Matrix c; c.init(); c.m[0][1] = a.m[0][1] + b.m[0][1]; c.m[0][2] = b.m[0][2] + a.m[0][2] + a.m[0][1] * b.m[1][2]; c.m[1][2] = a.m[1][2] + b.m[1][2]; return c; } vector<int> G[N]; int n, dfn[N], tol, id[N], top[N]; int son[N], fa[N], dep[N], sz[N]; ll ans[N]; struct Seg { #define lp p << 1 #define rp p << 1 | 1 Matrix tree[N << 2]; inline void pushdown(int p) { if (!tree[p].empty()) { tree[lp] = tree[lp] * tree[p]; tree[rp] = tree[rp] * tree[p]; tree[p].clear(); } } void update(int p, int l, int r, int x, int y, const Matrix &val) { if (x <= l && y >= r) { tree[p] = tree[p] * val; return; } int mid = l + r >> 1; pushdown(p); if (x <= mid) update(lp, l, mid, x, y, val); if (y > mid) update(rp, mid + 1, r, x, y, val); } void build(int p, int l, int r) { if (l == r) { ans[id[l]] = tree[p].m[0][2]; return; } int mid = l + r >> 1; pushdown(p); build(lp, l, mid); build(rp, mid + 1, r); } } seg; void dfs1(int u, int pre, int d) { dep[u] = d; fa[u] = pre; sz[u] = 1; for (auto v: G[u]) { dfs1(v, u, d + 1); sz[u] += sz[v]; if (sz[v] > sz[son[u]]) son[u] = v; } } void dfs2(int u, int tp) { top[u] = tp; dfn[u] = ++tol; id[tol] = u; if (!son[u]) return; dfs2(son[u], tp); for (auto v: G[u]) if (v != son[u]) dfs2(v, v); } void solve(int opt, int u, ll d) { Matrix c; c.init(); if (opt == 1) c.m[0][1] = d; else c.m[1][2] = d; int v = 1; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); seg.update(1, 1, n, dfn[top[u]], dfn[u], c); u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); seg.update(1, 1, n, dfn[u], dfn[v], c); } int main() { read(n); for (int i = 2; i <= n; i++) { int x; read(x); G[x].push_back(i); } dfs1(1, 0, 1); dfs2(1, 1); int q; read(q); while (q--) { int opt, u; ll d; read(opt), read(u), read(d); solve(opt, u, d); } seg.build(1, 1, n); for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11664626.html
