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
| #include <iostream>
#include <algorithm>
#include <vector>
#define maxn 100010
using namespace std;
const int p = 1000000007;
int n, c, q;
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 in[maxn], out[maxn], c2, dep[maxn];
void dfs(int u, int fa) {
in[u] = ++c2;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dep[v] = dep[u] + 1; dfs(v, u);
} out[u] = c2;
}
struct Point {
int x, y;
friend bool operator == (const Point &u, const Point &v) { return u.x == v.x && u.y == v.y; }
} a[maxn];
inline bool cmpx(const Point &u, const Point &v) {
if (u.x == v.x) return u.y < v.y;
return u.x < v.x;
}
inline bool cmpy(const Point &u, const Point &v) {
if (u.y == v.y) return u.x < v.x;
return u.y < v.y;
}
vector<bool(*)(const Point &u, const Point &v)> cmp;
void init_cmp() {
cmp.push_back(cmpx);
cmp.push_back(cmpy);
}
#define lc i << 1
#define rc i << 1 | 1
struct KDtree {
int xl, xr, yl, yr, v, tag;
Point p;
} T[maxn * 4];
inline void pushdown(int i) {
int &tag = T[i].tag; if (!tag) return ;
T[lc].tag = T[lc].v = tag;
T[rc].tag = T[rc].v = tag;
tag = 0;
}
void build(int i, int l, int r, int d) {
T[i].tag = 0;
if (l == r) return T[i] = { a[l].x, a[l].x, a[l].y, a[l].y, 1, 0, a[l] }, void();
int m = l + r >> 1; nth_element(a + l, a + m, a + r + 1, cmp[d]); T[i].p = a[m];
build(lc, l, m, d ^ 1); build(rc, m + 1, r, d ^ 1);
T[i].xl = min(T[lc].xl, T[rc].xl);
T[i].xr = max(T[lc].xr, T[rc].xr);
T[i].yl = min(T[lc].yl, T[rc].yl);
T[i].yr = max(T[lc].yr, T[rc].yr);
}
void update(int i, int xl, int xr, int yl, int yr, int v) {
if (max(T[i].xl, xl) > min(T[i].xr, xr) || max(T[i].yl, yl) > min(T[i].yr, yr)) return ;
if (xl <= T[i].xl && T[i].xr <= xr && yl <= T[i].yl && T[i].yr <= yr)
return T[i].v = T[i].tag = v, void();
pushdown(i);
update(lc, xl, xr, yl, yr, v); update(rc, xl, xr, yl, yr, v);
}
int query(int i, int l, int r, const Point &p, int d) {
if (l == r) return T[i].v;
int m = l + r >> 1; pushdown(i);
if (T[i].p == p || cmp[d](p, T[i].p))
return query(lc, l, m, p, d ^ 1);
else return query(rc, m + 1, r, p, d ^ 1);
}
void work() {
cin >> n >> c >> q; int ans = 0;
fill(head + 1, head + n + 1, -1);
c1 = c2 = 0;
for (int i = 2; i <= n; ++i) {
int x; cin >> x;
add_edge(x, i);
} dep[1] = 1; dfs(1, 0);
for (int i = 1; i <= n; ++i) a[i] = { in[i], dep[i] };
build(1, 1, n, 0);
for (int i = 1; i <= q; ++i) {
int c, x, y, v = 0; cin >> x >> y >> c;
if (!c) v = query(1, 1, n, { in[x], dep[x] }, 0);
else update(1, in[x], out[x], dep[x], dep[x] + y, c);
ans = (ans + 1ll * v * i) % p;
} cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T; init_cmp();
while (T--) work();
return 0;
}
|