给定一棵树与两个序列 \(a\set{n}\) 与 \(b\set{n}\)，定义 \(R\left(u\right)\) 为节点 \(u\) 的祖先集合，节点 \(u\) 的权值定义如下：
\[\left| \sum_{i \in R\left(u\right)} a_i \right| \times \left| \sum_{i \in R\left(u\right)} b_i \right| \]写一个数据结构支持 \(a\) 单点加与维护子树中的最大权值。
\(n \le 2 \times 10^5\)，\(q \le 10^5\)。
非常困难的题目。首先这种树上问题肯定是要用 DFS 序拍平成序列问题的。然后发现 \(b\) 始终不变，那么对于每一个 \(u\) 就可以预处理 \(\left| \sum_{i \in R\left(u\right)} b_i \right|\) 的值了，再然后 \(a_u\) 的变化只会影响 \(u\) 子树中的节点，那么问题就变成了区间加 \(a_i\)，区间询问最大权值。
我们发现这事实上是在区间维护一次函数，那么这非常的 KTT 啊，简直就是模板题，那么直接 KTT 均摊 \(\mathcal{O}\left(n \log^3 n\right)\) 完事了。
好吧多少还是得说一下。把权值看做一次函数，那么容易发现斜率 \(\left| \sum_{i \in R\left(u\right)} b_i \right|\) 不变，然后区间询问一次函数最大值相当于是在维护一个凸包，那么用类似 KTT 的方法在线段树内合并凸包即可。具体来说，我们需要在线段树节点内维护点值至少要增加多少，左儿子与右儿子中的最大值才会发生变化（即：如果之前左儿子值比右儿子大，那么点值至少增加多少才会使得右儿子值比左儿子大）。如果当前增加的点值超过了这个值，就递归下去修改，否则打上标记即可。
还有一个问题就是 \(\left| \sum_{i \in R\left(u\right)} a_i \right|\) 这一坨的绝对值符号，这个好说，因为 \(\left| \sum_{i \in R\left(u\right)} a_i \right| = \max\left\{\sum_{i \in R\left(u\right)} a_i, -\sum_{i \in R\left(u\right)} a_i\right\}\)，那么将一个函数拆成两个即可。
然后经过极其复杂的均摊分析可以得到复杂度线性三个 \(\log\)，看起来很大，但是 KTT 的一大特点就是跑不满，\(10^5\) 还是很稳的，那么做完了。