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
| #include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define maxn 50010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;
const int p = 201314;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
int n, m;
struct Fenwick_Tree {
int B1[maxn], B2[maxn];
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i))
B1[i] = ::add(B1[i], v), B2[i] = ::add(B2[i], mul(x, v));
}
int get_sum(ll x) {
int s = 0;
for (int i = x; i; i -= lowbit(i))
s = ::add(s, mul(x + 1, B1[i])), s = ::add(s, p - B2[i]);
return s;
}
void update(int l, int r, int v) { add(l, v), add(r + 1, p - v); }
int query(int l, int r) { return ::add(get_sum(r), p - get_sum(l - 1)); }
} B;
struct Edge {
int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
int dep[maxn], son[maxn], sz[maxn], f[maxn];
void dfs(int u, int fa) {
int Max = 0; sz[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
f[v] = u, dep[v] = dep[u] + 1;
dfs(v, u); sz[u] += sz[v];
if (sz[v] > Max) Max = sz[v], son[u] = v;
}
}
int top[maxn], id[maxn], bl[maxn];
void dfs(int u, int fa, int topf) {
static int cnt = 0;
top[u] = topf, id[u] = ++cnt, bl[cnt] = u;
if (son[u]) dfs(son[u], u, topf);
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || v == son[u]) continue;
dfs(v, u, v);
}
}
void update(int x, int v) {
while (top[x] != 1) {
B.update(id[top[x]], id[x], v);
x = f[top[x]];
} B.update(id[1], id[x], v);
}
int query(int x) {
int s = 0;
while (top[x] != 1) {
s = add(s, B.query(id[top[x]], id[x]));
x = f[top[x]];
} s = add(s, B.query(id[1], id[x]));
return s;
}
vector<tuple<int, int, int>> A[maxn];
int ans[maxn];
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 2, x; i <= n; ++i) cin >> x, ++x, add_edge(x, i);
for (int i = 1; i <= m; ++i) {
int x, y, z; cin >> x >> y >> z; ++x, ++y, ++z;
A[y].emplace_back(z, 1, i);
A[x - 1].emplace_back(z, p - 1, i);
} dep[1] = 1, dfs(1, 0), dfs(1, 0, 1);
for (int i = 1; i <= n; ++i) {
update(i, 1);
for (auto [t, v, id] : A[i]) ans[id] = add(ans[id], mul(v, query(t)));
}
for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
return 0;
}
|