我咋叕写挂简单题了。

· · 题解

这个题 800 吧。

  • 给你一棵 n 个点的有根树，根为 1，边带权。每个点有点权 a_i，初始 a_i=0。记 \text{dis}(x,y) 表示 x,y 简单路径上的边权和。
  • - `1 x y`：对于 $x$ 子树内的点 $u$，$a_u\leftarrow a_u+\text{dis}(u,y)$。 - `2 x`：查询 $x$ 子树内的点的点权和。

省流：

记 f_u 为 u 的父亲，w_u 为 u\rightarrow f_u 这条边的权值，不妨 f_1=0；s_x 为以 x 为根的子树大小。直接考虑每个点的点权变化没那么容易，但是注意到在一个修改操作中，f_u 和 u 点权变化量总是差一个 w_u 或 -w_u。这启示我们将点权做差分。

令 d_i=a_{u}-a_{f_u}，记 u 根链上的点依次是 p_1=1,\dots,p_k=u。那么 a_u=\sum\limits_{i=1}^kd_{p_i}。

先考虑比较简单的情形，即 y 在 x 子树外。此时 d_x 增加 \text{dis}(x,y)。对于 x 子树内的其他点 u，d_u 增加 w_u。

再考虑 y 在 x 子树内的情况，也就是省流的那张图。我们发现不在 x\rightsquigarrow y 路径上的点 u，d_u 仍然增加 w_u。而在路径上的点（不包括 x），d_u 会减少 w_u。

考虑我们要查询什么，即子树内所有点的根链 d 值和的和。考虑每个点 u 的 d_u 会对哪些点产生贡献。若 u 在 1\rightsquigarrow x 上，那么会对整棵子树的点都产生贡献，为 d_us_x。若其在 x 子树内，它会对以 u 为根的子树内的点产生贡献，为 d_us_u。

现在问题来链、子树 d_u 加 kw_u+b，链查 \sum d_u，子树查 \sum d_us_u。重链剖分，问题变为区间 d_u 加 kw_u+b，区间查 \sum d_u 和 \sum d_us_u。使用你喜欢的数据结构维护即可。我是用的是树状数组。

::::info[怎么维护] 相当于给出三个数列 d_i,s_i,w_i，其中 w_i,s_i 为常数列。d_i 要支持的操作为区间加 Aw_i+B，求区间 \sum d_is_i。\sum d_u 就是的 s_u=1 的情况。

直接维护 d_is_i 前缀和 \operatorname{DS}_i。考虑一个操作对前缀和序列造成哪些影响。假设操作区间为 [l,r]。

记 S_i 为 s_i 的前缀和，\operatorname{WS}_i 为 w_is_i 的前缀和。

对于 i\in [r+1,n] 这部分，P_i 的增量为 d_ls_l\sim d_rs_r 的增量之和，为 B(S_r-S_{l-1})+A(\operatorname{WS}_r-\operatorname{WS}_{l-1})。

对于 i\in [l,r] 这部分，P_i 的增量为 d_ls_l\sim d_is_i 的增量之和，为 B(S_i-S_{l-1})+A(\operatorname{WS}_i-\operatorname{WS}_{l-1})。

我们维护 P_i=A_i\operatorname{WS}_i+B_iS_i+C_i，则操作可以表示为 A_i,B_i,C_i 的区间加。由于维护的是前缀和数组，求原数组的区间和只需要单点查。所以只需要区间加、单点查。就可以树状数组维护了。 ::::

认为 n,q 同阶，时间复杂度 \mathcal{O}\left(q\log^2 n\right)，空间复杂度 \mathcal{O}(n)。常数比线段树小，跑到了最优解。