[LNOI 2014]LCA

Description

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。
(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)

Input

第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。

Output

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

Sample Input

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

Sample Output

8
5

HINT

共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。

题解

[HNOI 2015]开店的简化版。

 //It is made by Awson on 2018.1.8 #include <set> #include <map> #include <cmath> #include <ctime> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define RE register #define lowbit(x) ((x)&(-(x))) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) using namespace std; ; ; ; ], dep[N+], top[N+], cnt, size[N+], son[N+], pos[N+]; struct tt {     int to, next; }edge[N+]; ], tot; void add(int u, int v) {     edge[++tot].to = v;     edge[tot].next = path[u];     path[u] = tot; } struct Segment_tree {     ], sum[N*+], lazy[N*+], ch[N*][], pos;     int newnode(int r) {     ] = ch[r][], ch[o][] = ch[r][];     return o;     }     void update(int &o, int l, int r, int a, int b, int last) {        if (o <= last) o = newnode(o);     if (a <= l && r <= b) {         sum[o] += r-l+, sum[o] %= MOD, lazy[o]++; return;     }     ;     ], l, mid, a, b, last);     ], mid+, r, a, b, last);     sum[o] = (sum[ch[o][]]+sum[ch[o][]]+(LL)lazy[o]*(r-l+)%MOD)%MOD;     }     int query(int o, int l, int r, int a, int b) {     ;     if (a <= l && r <= b) return sum[o];     , c1 = , c2 = ;     ], l, mid, a, b);     ], mid+, r, a, b);     )%MOD)%MOD;     } }T; void dfs1(int o, int father, int depth) {     fa[o] = father, dep[o] = depth+, size[o] = ;     for (int i = path[o]; i; i = edge[i].next) {     dfs1(edge[i].to, o, depth+);     size[o] += size[edge[i].to];     if (size[edge[i].to] > size[son[o]]) son[o] = edge[i].to;     } } void dfs2(int o, int tp) {     top[o] = tp, pos[o] = ++cnt;     if (son[o]) dfs2(son[o], tp);     for (int i = path[o]; i; i = edge[i].next)     if (edge[i].to != son[o]) dfs2(edge[i].to, edge[i].to); } , n, pos[top[o]], pos[o], last), o = fa[top[o]]; } int lca_query(int id, int o) {     ;     , n, pos[top[o]], pos[o]), ans %= MOD, o = fa[top[o]];     return ans; } void work() {     scanf("%d%d", &n, &q);     ; i <= n; i++) scanf(, i);     dfs1(, , ), dfs2(, );     ; i <= n; i++) {     T.root[i] = T.root[i-]; lca_update(i, i, T.pos);     }     while (q--) {     scanf("%d%d%d", &u, &v, &c);     printf(, c+)-lca_query(u, c+)+MOD)%MOD);     } } int main() {     work();     ; }