#P3626. [LNOI2014]LCA

    ID: 1784 传统题 1000ms 128MiB 尝试: 4744 已通过: 1277 难度: 7 上传者: 标签>CF2200提高+/省选-贡献法一维前缀和离线查询树链剖分懒标记线段树数据已加强by

[LNOI2014]LCA

题目描述

给出一个 nn 个节点的有根树(编号为 00 到 n−1n-1,根节点为 00)。一个点的深度定义为这个节点到根的距离 +1+1。

设 depidep_i 表示点 ii 的深度,LCA(i,j)LCA(i,j) 表示 ii 与 jj 的最近公共祖先。

有 qq 次询问,每次询问给出 l,r,zl,r,z,求 ∑i≤ri=ldep[LCA(i,z)]\sum_{i\le r}^{i=l}dep[LCA(i,z)]。

(即,求在 [l,r][l,r]区间内的每个节点 ii 与 zz 的最近公共祖先的深度之和)

输入格式

第一行两个整数 n,qn,q。

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

接下来 qq 行,每行三个整数 l,r,zl,r,z。

输出格式

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

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

数据规模与约定

共 55 组数据,nn 与 qq 的规模分别为 10000,20000,30000,40000,5000010000,20000,30000,40000,50000。

题目来源

数据已加强 by saffah