Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Now you are given a rooted tree with N nodes(rank them from 0 to N-1). The depth of a node x is define as distance(x, root) + 1. The 0th node is always the root of the tree.
We have Q queries: given node x, and two integers L and R, you should calculate the value .
LCA(x,y) means the least common ancestor of node x and node y which is the common ancestor of x and y with maximum depth value.
The first line contains two integers N and Q. (1 <= N, Q <= 50000)
The next N – 1 line each line contains an integer p indicate the father of node i. The integer in 2nd line indicating the father of node 1, 3rd line indicating the father of node 2, and so on.
The next Q lines each line contains three integers L, R, x which describe a query. (L <= R)
For each query, you should output the answer moduled 201314.
1 4 4
1 3 4
2 2 3
1 4 2