:::info[约定]
记：
- \(rt\) 为树根
- \(a_x\) 为 \(x\) 原本权值
- \(fa[x],fa_x\) 为 \(x\) 父亲
- \(tr[x]\) 为 \(x\) 子树集合
- \(son[x]\) 为 \(x\) 的儿子集合
- \(d_x\) 为 \(x\) 点深度
- DS 泛指线段树、树状数组
:::
操作、查询无链
只会有单点与子树操作，通过 dfs 序将子树拍到序列上，成为区间问题，用任意 DS 维护。
链操作，单点查询
首先链可以拆成两条从上到下的路径，对它进行操作即可。
链、单点
记 \(cf_x=a_x-\sum_{s \in son[x]} a_s\)。如果更改的链为 \(u\sim v\)（\(v\) 为 \(u\) 祖先），查询的点为 \(p\)
- 链加变为更改 \(cf_{fa[v]},cf_u\)
- 单点查变为 \(p\) 的子树和
问题转化为单点加、子树和的形式，回到“操作、查询无链”。
单点加链和
记 \(s_x=a_x+sum_{fa[x]}\)，即 \(x\) 到 \(rt\) 的权值和。
- 单点加变为 \(p\) 子树加
- 链查询变为单点求 \(sum_u-sum_{fa[x]}\)
转化为子树加、单点和。
总结
操作、查询中带有链与单点，就将链转化为单点、单点转化为子树，使用单点与子树的方法解决。
链、子树
重要！链依旧可以拆成两个。
链加子树和
记 \(cf_x=a_x-\sum_{s \in son[x]} a_s\)
- 链加转化为单点加
- 子树和转化为子树和的子树和（先用差分做子树和算出原数组，在用原数组算出子树和）
对于子树和的子树和，考虑维护两个树状数组，BIT1 维护 \(cf_x\)，BIT2 维护 \(cf_x\times d_x\)。单点加时直接修改两个BIT 的值，答案推式子可得：
\[\begin{aligned}
\sum_{s\in tr[x]} \sum_{t\in tr[s]} cf_t
&=\sum_{s\in tr[x]} cf_s(d_s-d_{fa[x]})\\
&=\sum_{s\in tr[x]} cf_s\times d_s-d_{fa[x]}\sum_{s\in tr[x]} cf_s
\end{aligned}\]
于是问题转化为了单点修改子树查询。
子树加链和
记 \(s_x=a_x+sum_{fa[x]}\)
- 链和转化为单点和
- 子树加转化为子树的子树加（原本的子树加，在前缀和上高的点会对低的点前缀和产生影响，加更多）
依旧用 BIT1 维护 \(s_x\)，BIT2 维护 \(s_x\times d_x\)。先考虑答案为 \(s_u-s_{fa[v]}\)（\(v\) 为 \(u\) 祖先）。
当 \(tr[x]\) 整体加 \(\alpha\) 时，有伪代码
\[\begin{aligned}
\begin{aligned}
&(\forall_{u\in tr[x]}\forall_{t\in tr[u]} s_t+=\alpha)\\
&\Rightarrow (\forall_{u\in tr[x]} s_u)+=(\alpha \times (d_u-d_{fa[x]}))\\
&\Rightarrow (\forall_{u\in tr[x]} s_u)+=\alpha\times d_u;(\forall_{u\in tr[x]} s_u)-=\alpha\times d_{fa[x]}
\end{aligned}
\end{aligned}\]
其中分号前的部分就是对 BIT2 的修改。问题再次转化为子树修改单点查询。
链修改、链查询
树链剖分即可。注意查询修改复杂度是 \(O(\log^2 n)\)