YZOJ P3484 子树求和

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)\) 。

 

 

 

 

《YZOJ P3484 子树求和》上有2条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注