YZOJ P3484 子树求和

时间限制：2000MS      内存限制：262144KB      出题人：lgj

难度： \(6.0\)

• 题目描述

已知一棵树有 \(n\) 个节点，并且根节点是固定的。

每个节点上都有一个权值 \(w_i\) ，记 \(s_i\) 为 以 \(i\) 为根的子树中，所有节点的 \(w_i\) 的和。

由于询问 \(s_i\) 太简单了，不能将 AKIOI 的你的高智商体现出来，所以每次询问给定 \(l, r\) ，求 \(\sum\limits_{i=l}^{r}{s_i}\) 。

为了避免此题难度太低，不能将 AKIOI 的你的高智商体现出来，所以的询问的过程中还可能修改某个节点的 \(w_i\) 。

为了将 AKIOI 的你的高智商体现出来，你要写一个程序来实时给出询问的答案。

• 输入格式

第一行为两个整数 \(n\) 和 \(q\)，分别表示节点数和操作的次数；

第二行 \(n\) 个正整数，表示序列 \(w\) ；

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(u_i\) 和 \(v_i\)，描述一条树上的边。特别地，\(u_i=0\) 时，表示 \(v_i\) 为树的根节点；

接下来 \(q\) 行，每行三个正整数 \(op, l, r\) 。描述 \(q\) 组操作。 \(op=1\) 表示 \(w_l\) 修改为 \(r\)，\(op=2\) 表示询问 \(\sum\limits_{i=l}^{r}{s_i}\) 的值。

• 输出格式

对于每组询问操作，你需要依据当前树的情况输出该组询问的标准答案，每次询问的答案独占一行。

• 样例输入

• 样例输出

（假样例）

• 数据规模与约定

对于 \(40\%\) 的数据，\(n, q \leq 3000\) ；

对于另外 \(15\%\) 的数据，所有 \(op=2\) 的操作 \(l=r\) ；

对于 \(100\%\) 的数据，\(n, q \leq 100000\)，\( w_i \leq 10^9\) 。

 

 

 

---

 

 

 

首先把每个节点的 dfn 求出来，那么一个节点的子树就对于其中连续的一段区间。差分预处理修改每个点会对其他节点造成多少的影响，分块维护 dfn 序列，由于查询比较多（每次查询一个编号都会对应查询这里的一段区间），所以前缀和维护分块。同时分块维护编号序列，由于每次只会修改一个编号，所以使用普通的分块即可。

修改的时间复杂度：编号 \(O(1)\)，dfn \(O(\sqrt n)\) ；

查询的时间复杂度：编号 \(O(\sqrt n)\) ， dfn \(O(1)\) ；

总时间复杂度 \(O(n\sqrt n)\) 。