#1850. [LNOI2014]LCA

    ID: 1850 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数据结构线段树树结构最近公共祖先树链剖分概率论组合数学差分2014各省省选辽宁LCA树剖统计

[LNOI2014]LCA

题目描述

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

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

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

mm 次询问,每次询问给出 l r zl\ r\ z,求 i=lrdep[LCA(i,z)]\sum_{i=l}^r dep[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