#P4211. [LNOI2014] LCA

    ID: 3142 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2014线段树各省省选辽宁最近公共祖先,LCA树链剖分,树剖概率论,统计差分

[LNOI2014] LCA

题目描述

给出一个 nn 个节点的有根树(编号为 00n1n-1,根节点为 00)。

一个点的深度定义为这个节点到根的距离 +1+1

dep[i]dep[i] 表示点 ii 的深度,LCA(i,j)\operatorname{LCA}(i, j) 表示 iijj 的最近公共祖先。

mm 次询问,每次询问给出 l,r,zl, r, z,求 i=lrdep[LCA(i,z)]\sum_{i=l}^r dep[\operatorname{LCA}(i,z)]

输入格式

第一行 22 个整数,n,mn, m

接下来 n1n-1 行,分别表示点 11 到点 n1n-1 的父节点编号。

接下来 mm 行,每行 33 个整数,l,r,zl, r, z

输出格式

输出 qq 行,每行表示一个询问的答案。每个答案对 201314201314 取模输出。

5 2
0
0
1
1
1 4 3
1 4 2
8
5

提示

对于 20%20\% 的数据,n10000,m10000n\le 10000,m\le 10000

对于 40%40\% 的数据,n20000,m20000n\le 20000,m\le 20000

对于 60%60\% 的数据,n30000,m30000n\le 30000,m\le 30000

对于 80%80\% 的数据,n40000,m40000n\le 40000,m\le 40000

对于 100%100\% 的数据,1n50000,1m500001\le n\le 50000,1\le m\le 50000