编程之美初赛第一场 树[通俗易懂]

编程之美初赛第一场 树

大家好,又见面了,我是全栈君。

题目2 : 树

时间限制:
4000ms
单点时限:
2000ms
内存限制:
256MB

描写叙述

有一个N个节点的树。当中点1是根。初始点权值都是0。

一个节点的深度定义为其父节点的深度+1,。特别的。根节点的深度定义为1。

如今须要支持一系列下面操作:给节点u的子树中,深度在l和r之间的节点的权值(这里的深度依旧从整个树的根节点開始计算)。都加上一个数delta。

问完毕全部操作后,各节点的权值是多少。

为了降低巨大输出带来的开销。如果完毕全部操作后。各节点的权值是answer[1..N],请你依照例如以下方式计算出一个Hash值(请选择合适的数据类型。注意避免溢出的情况)。终于仅仅须要输出这个Hash值就可以。

MOD =1000000007; // 10^9 + 7

MAGIC= 12347;

Hash =0;

For i= 1 to N do

   Hash = (Hash * MAGIC + answer[i]) mod MOD;

EndFor

输入

第一行一个整数T (1 ≤ T ≤ 5)。表示数据组数。

接下来是T组输入数据。測试数据之间没有空行。

每组数据格式例如以下:

第一行一个整数N (1 ≤ N ≤ 105)。表示树的节点总数。

接下来N – 1行,每行1个数。a (1 ≤ a ≤ N),依次表示2..N节点的父亲节点的编号。

接下来一个整数Q(1 ≤ Q ≤ 105),表示操作总数。

接下来Q行,每行4个整数。u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109),代表一次操作。

输出

对每组数据。先输出一行“Case x: ”,x表示是第几组数据,然后接这组数据答案的Hash值。

数据范围

小数据:1 ≤ N, Q ≤ 1000

大数据:1 ≤ N, Q ≤ 105


例子解释

点1的子树中有1,2,3三个节点。当中深度在2-3之间的是点2和点3。

点2的子树中有2,3两个节点。当中没有深度为1的节点。

所以,运行全然部操作之后,仅仅有2,3两点的权值添加了1。即答案是0 1 1。再计算相应的Hash值就可以。

例子输入
1
3
1
2
2
1 2 3 1
2 1 1 1
例子输出
Case 1: 12348

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115562.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • C++和java的区别和联系「建议收藏」

    C++和java的区别和联系「建议收藏」最近在看C++和java的基础知识,对它们面向对象编程的概念还不是很了解,但觉得它们之间有很多相通的地方,现在java比较热门,觉得使用java的框架可以做很多很多事情,而对C++的认识只知道在游戏开发上面用的比较多,自己接触编程还是太少,想要一点一点地积累进步,需要向很多大神和牛人学习经验。

  • TFRecord简介,原理分析,代码实现?[通俗易懂]

    TFRecord简介,原理分析,代码实现?在利用深度学习算法搭建完成网络之后,我们要对网络进行训练,要训练网络就要有训练数据,通常我们会直接对硬盘上存放数据进行操作,来fetch到网络中。这样直接从硬盘上读取数据太慢了,为了加快数据读取,今天我们介绍一种比较好的数据格式tfrecord,那么什么是tfrecord呢?什么TFRecord格式的数据?Tensorfl…

  • 【目标检测】Labelme的改进——海量图片的自动标注「建议收藏」

    【目标检测】Labelme的改进——海量图片的自动标注「建议收藏」  深度学习一般需要对大量的图片进行标注,但是手动标注耗时耗力,所以模仿labelme软件的功能,使用程序对大批量的图片进行自动标注,大大减少手动操作。下面介绍如何实现对大批量的图片进行标注。自动标注的程序实现:https://github.com/shuyucool/Labelme.git程序内容均为原创,如果使用麻烦您点赞呀如遇疑问,欢迎随时交流,定尽量解答。联系方式:7819…

  • Eclipse乱码怎么办

    Eclipse乱码怎么办Android与H5交互前言一.设置工作空间的编码前言在Eclipse中导入新的项目的时候,会遇到乱码的问题,而乱码的问题主要集中在中文的显示上。不过通过设置编码方式,看似十分恐怖的乱码问题也能够轻易解决。Eclipse设置编码的地方主要有三处,这三处的设置都会影响中文的显示。一.设置工作空间的编码编辑器的编码会影响到所有的项目中的字符的显示,可以说是作用最为广泛的设置,每一个项目都会…

  • Android layout属性之gravity和layout_gravity「建议收藏」

    Android layout属性之gravity和layout_gravity「建议收藏」1.gravity用来描述当前view的内容在view中的位置。gravity是控制其内容或者包含的views在该view(或viewgroup)中的位置2.layout_gravity是表示

  • windows本地 Oracle 11g安装完整教程 (windows10下安装)「建议收藏」

    windows本地 Oracle 11g安装完整教程 (windows10下安装)「建议收藏」转载于http://www.cnblogs.com/miye/p/6977920.html1.下载Oracle11gR2forWindows版本,下载地址如下官方网站:http://download.oracle.com/otn/nt/oracle11g/112010/win32_11gR2_database_1of2.ziphttp://download.oracle.com/otn/n…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号