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
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
5
HINT
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
题解
[HNOI 2015]开店的简化版。
1 //It is made by Awson on 2018.1.8 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <cstdio> 9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define RE register 17 #define lowbit(x) ((x)&(-(x))) 18 #define Max(a, b) ((a) > (b) ? (a) : (b)) 19 #define Min(a, b) ((a) < (b) ? (a) : (b)) 20 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) 21 using namespace std; 22 const int N = 50000; 23 const int MOD = 201314; 24 const int INF = ~0u>>1; 25 26 int n, q, f, u, v, c, fa[N+5], dep[N+5], top[N+5], cnt, size[N+5], son[N+5], pos[N+5]; 27 struct tt { 28 int to, next; 29 }edge[N+5]; 30 int path[N+5], tot; 31 void add(int u, int v) { 32 edge[++tot].to = v; 33 edge[tot].next = path[u]; 34 path[u] = tot; 35 } 36 struct Segment_tree { 37 int root[N+5], sum[N*150+5], lazy[N*150+5], ch[N*150][2], pos; 38 int newnode(int r) { 39 int o = ++pos; sum[o] = sum[r], lazy[o] = lazy[r], ch[o][0] = ch[r][0], ch[o][1] = ch[r][1]; 40 return o; 41 } 42 void update(int &o, int l, int r, int a, int b, int last) { 43 if (o <= last) o = newnode(o); 44 if (a <= l && r <= b) { 45 sum[o] += r-l+1, sum[o] %= MOD, lazy[o]++; return; 46 } 47 int mid = (l+r)>>1; 48 if (mid >= a) update(ch[o][0], l, mid, a, b, last); 49 if (mid < b) update(ch[o][1], mid+1, r, a, b, last); 50 sum[o] = (sum[ch[o][0]]+sum[ch[o][1]]+(LL)lazy[o]*(r-l+1)%MOD)%MOD; 51 } 52 int query(int o, int l, int r, int a, int b) { 53 if (!o) return 0; 54 if (a <= l && r <= b) return sum[o]; 55 int mid = (l+r)>>1, c1 = 0, c2 = 0; 56 if (mid >= a) c1 = query(ch[o][0], l, mid, a, b); 57 if (mid < b) c2 = query(ch[o][1], mid+1, r, a, b); 58 return (c1+c2+(LL)lazy[o]*(Min(r, b)-Max(l, a)+1)%MOD)%MOD; 59 } 60 }T; 61 void dfs1(int o, int father, int depth) { 62 fa[o] = father, dep[o] = depth+1, size[o] = 1; 63 for (int i = path[o]; i; i = edge[i].next) { 64 dfs1(edge[i].to, o, depth+1); 65 size[o] += size[edge[i].to]; 66 if (size[edge[i].to] > size[son[o]]) son[o] = edge[i].to; 67 } 68 } 69 void dfs2(int o, int tp) { 70 top[o] = tp, pos[o] = ++cnt; 71 if (son[o]) dfs2(son[o], tp); 72 for (int i = path[o]; i; i = edge[i].next) 73 if (edge[i].to != son[o]) dfs2(edge[i].to, edge[i].to); 74 } 75 void lca_update(int id, int o, int last) {while (top[o]) T.update(T.root[id], 1, n, pos[top[o]], pos[o], last), o = fa[top[o]]; } 76 int lca_query(int id, int o) { 77 int ans = 0; 78 while (top[o]) ans += T.query(T.root[id], 1, n, pos[top[o]], pos[o]), ans %= MOD, o = fa[top[o]]; 79 return ans; 80 } 81 void work() { 82 scanf("%d%d", &n, &q); 83 for (int i = 2; i <= n; i++) scanf("%d", &f), add(f+1, i); 84 dfs1(1, 0, 1), dfs2(1, 1); 85 for (int i = 1; i <= n; i++) { 86 T.root[i] = T.root[i-1]; lca_update(i, i, T.pos); 87 } 88 while (q--) { 89 scanf("%d%d%d", &u, &v, &c); 90 printf("%d ", (lca_query(v+1, c+1)-lca_query(u, c+1)+MOD)%MOD); 91 } 92 } 93 int main() { 94 work(); 95 return 0; 96 }