#P10395. [2021年联测]sumsum

    ID: 9515 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-贡献法点分治点分治容斥去重一维前缀和LCA树上倍增

[2021年联测]sumsum

题目描述

给定一棵有 nn 个节点的无向树,节点编号为 1,…,n1,\ldots,n,初始点权为 a1,…,ana_1,\ldots,a_n。另给定两个整数 L,RL,R。

每次操作给出 u,v,du,v,d,先把树上从 uu 到 vv 的唯一路径上的所有点权增加 dd,包括两个端点。然后求所有包含 LL 到 RR 个节点的简单路径的权值之和。一条路径的权值是它包含的点权之和。路径不区分方向,单个节点也是一条包含一个节点的路径。

点权更新持续生效。每次操作后,将所求的总和对 Q=109+7Q=10^9+7 取模。

输入格式

第一行四个整数 n,m,L,Rn,m,L,R。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

第三行 n−1n-1 个整数 f1,…,fn−1f_1,\ldots,f_{n-1},其中 fif_i 表示节点 i+1i+1 与节点 fif_i 有一条边。

接下来 mm 行,每行三个整数 u,v,du,v,d,表示一次操作。

输出格式

输出 mm 行,每行一个整数,表示相应操作后的答案。

样例

10 10 3 6
36 11 76 24 71 89 24 63 75 40
1 1 2 2 3 3 4 4 5
2 5 18
5 7 95
7 10 82
8 2 99
8 1 85
7 7 60
1 5 85
4 3 38
9 4 17
1 1 99
7591
17186
26124
32163
39473
39953
46073
49835
50328
52803

数据范围

1≤L≤R≤n1\le L\le R\le n,0≤ai,d<Q0\le a_i,d<Q,1≤fi≤i1\le f_i\le i,1≤u,v≤n1\le u,v\le n。

原测试点 nn mm 附加性质
1 10
2 50
3 300
4 2000 2000
5 10510^5
6 10510^5 fi=if_i=i
7 fi=⌊(i+1)/2⌋f_i=\lfloor(i+1)/2\rfloor
8 相同的 fif_i 至多出现两次
9–10

原 PDF 题面