首页 > 试题广场 >

树上求和

[编程题]树上求和
给你一棵根为1的有N个节点的树，以及Q次操作。
每次操作诸如:
1 x y：将节点x所在的子树的所有节点的权值加上y
2 x：询问x所在子树的所有节点的权值的平方和，答案模23333后输出

输入描述:
第一行两个整数N,Q
第二行N个整数，第i个表示节点i的初始权值
接下来N-1行每行两个整数u,v，表示u和v之间存在一条树边
接下来Q行每行一个操作，格式如题目描述


输出描述:
对于每个询问操作，输出一行一个整数，表示答案在模23333后的结果
示例1

输入

5 5
0 0 0 0 0
1 2
1 3
3 4
3 5
1 1 3
1 3 7
1 4 5
1 5 6
2 1

输出

599

备注:
1. 数据范围
一共有10个测试点，对于第i个测试点保证，N=10000 x i
对于的数据，有1 ≤ N,Q,y ≤ 105,1 ≤ x ≤ N
2. 注
平方和的意思是：a2+b2+c2
是和的平方
算法知识视频讲解
开通博客
头像 Clouder0
发表于 2020-07-14 21:33:04
其实这是我打的第二道题……一眼可以用树剖做，于是就是树链剖分的板子题。但其实似乎只求子树用dfs序就可以……？是我蠢了。线段树维护平方和也是老套路了： #include <cstdio> #include <ctype.h> #define DEBUG #define in 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 sunsetcolors
发表于 2020-07-14 23:31:33
D 树上求和 题目地址： https://ac.nowcoder.com/acm/contest/6290/D 基本思路： 比较裸的一道题，没有什么思维量，首先要维护子树状态，很明显我们可以求个序，然后用数据结构去维护，观察一下题意，要维护区间平方和，进行区间查询和区间修改，所以考虑线段树。 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

线段树
难度：
0条回答 15浏览

热门推荐

相关试题

树上求和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号