首页 > 试题广场 >

点权和

[编程题]点权和

给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和.


输入描述:
第一行两个数n和m
第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1
第三行m个数，每个数x依次表示这次操作的点是x


输出描述:
输出一个数，即这m次操作的答案的hash值
如果是第i次操作，这次操作结果为ans,则这个hash值加上
i * ans
输出hash值对19260817取模的结果
示例1

输入

6 3
1 1 2 3 3
1 2 3

输出

34
示例2

输入

6 10
1 1 2 3 3
1 4 6 5 2 3 3 3 3 3

输出

869

备注:
n <= 100000
m <= 10000000
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

倍增
上传者：牛客301599号
难度：
0条回答 2浏览

热门推荐

通过挑战的用户

查看代码

相关试题

点权和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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