1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//LCT
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 100000
#define mod 201314
using namespace std;
int N, ans[maxn], z[maxn], Q;
vector<int> l[maxn], r[maxn];
struct node
{
int rev, sum, add, size, w;
node *f, *ch[2];
}nd[maxn], *s[maxn];
inline int getwh(node *x)
{if(!x->f)return -1;if(x->f->ch[0]==x)return 0;if(x->f->ch[1]==x)return 1;return -1;}
inline bool isroot(node *x){return getwh(x)==-1;}
inline void join(node *x, node *y, int wh){if(x)x->f=y;if(y)y->ch[wh]=x;}
inline void rev(node *x){if(x)x->rev^=1;}
inline void add(node *x, int d){if(x)x->add+=d;}
inline void pushdown(node *x)
{
if(!x)return;
if(x->rev)
{
swap(x->ch[0],x->ch[1]);
rev(x->ch[0]),rev(x->ch[1]);
x->rev=0;
}
if(x->add)
{
x->sum+=x->size*x->add;
x->w+=x->add;
add(x->ch[0],x->add),add(x->ch[1],x->add);
x->add=0;
}
}
inline void pushup(node *x)
{
pushdown(x->ch[0]),pushdown(x->ch[1]);
x->size=1;x->sum=x->w;
if(x->ch[0])x->size+=x->ch[0]->size,x->sum+=x->ch[0]->sum;
if(x->ch[1])x->size+=x->ch[1]->size,x->sum+=x->ch[1]->sum;
}
inline void rotate(node *x)
{
node *y=x->f, *z=y->f; int c=getwh(x);
if(isroot(y))x->f=z;else join(x,z,getwh(y));
join(x->ch[!c],y,c),join(y,x,!c);
pushup(y),pushup(x);
}
inline void splay(node *x)
{
node *y; int top=0;
for(y=x;!isroot(y);y=y->f)s[++top]=y;s[++top]=y;
for(;top;top--)pushdown(s[top]);
while(!isroot(x))
{
y=x->f;
if(isroot(y)){rotate(x);return;}
if(getwh(x)^getwh(y))rotate(x);else rotate(y);
rotate(x);
}
}
inline void access(node *x)
{
node *t=0;
while(x)
{
splay(x);
x->ch[1]=t;
pushup(x);
t=x,x=x->f;
}
}
inline void makeroot(node *x){access(x);splay(x);rev(x);}
inline void link(node *x, node *y){makeroot(x);x->f=y;}
int read(int x=0)
{
char c=getchar();
while(c<48 or c>57)c=getchar();
while(c>=48 and c<=57)x=(x<<1)+(x<<3)+c-48,c=getchar();
return x;
}
void init()
{
int i, x, y;
N=read(), Q=read();
for(i=2;i<=N;i++)link(nd+i,nd+read()+1);
for(i=1;i<=Q;i++)
{
x=read()+1, y=read()+1, z[i]=read()+1;
l[x-1].push_back(i);
r[y].push_back(i);
}
}
void work()
{
int i, q; vector<int>::iterator it;
node *root=nd+1;
for(i=1;i<=N;i++)
{
access(nd+i);splay(root);root->add++;
for(it=l[i].begin();it!=l[i].end();it++)
{
q=*it;
access(nd+z[q]);splay(root);
ans[q]-=root->sum;
}
for(it=r[i].begin();it!=r[i].end();it++)
{
q=*it;
access(nd+z[q]);splay(root);
ans[q]+=root->sum;
}
}
}
int main()
{
int i;
init();
work();
for(i=1;i<=Q;i++)printf("%dn",ans[i]%mod);
return 0;
}