Description

给定一棵 $n$ 个点的树 $T$，每个点的权值为二元组 $(a_i,b_i)$.
定义 $R(u)$ 为 $u$ 的所有祖先节点（包括 $u$）的集合.
定义 $u$ 的权值为
$$W(u)=\left|\sum _{i\in R(u)}{a}_i\right|\times \left|\sum _{i\in R(u)}{b}_i\right|$$

你需要执行 $q$ 个操作，分两种：

• 1 u x：执行 $a_u\leftarrow a_u+x$.
• 2 u：求 $\underset{i\in \mathrm{subtree}(u)}{\max }W(i)$.

Limitations

$1\le n\le 2\times 10^5$
$1\le q\le 10^5$
$|a_i|,|b_i|\le 5000$
$1\le x\le 5000$

Solution

记 $P(u)=\sum _{i\in R(u)}{a}_i,Q(u)=\sum _{i\in R(u)}{b}_i$.
首先这个 $Q(u)$ 是假的，由于只会修改 $a$，所以 $W(u)$ 可以视作关于 $|P(u)|$ 的一次函数.

考虑直接维护 $P(u)$ 和 $Q(u)$，那么对 $a$ 的单点加相当于对 $P(u)$ 的子树加，直接拍到 dfs 序上.

现在问题转化为给 $P(u)$ 区间加，查询区间 $\max |P(u)|\times |Q(u)|$.
注意到 $|x|=\max (x,-x)$，由于只会加正数，可以用两棵 KTT 维护函数 $y=P(u)\times |Q(u)|$ 和 $y=-P(u)\times |Q(u)|$，查询时对两个 $y$ 取最大的即可.

时间复杂度约为 $O((n+q){\log }^{3}n)$，但是卡不满，可以过.

Submission