多组数据真tm恶心~
把 $dfs$序和深度分别看作横纵坐标，然后用 $KDtree$ 数点就可以了~
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 300005
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int d;
struct Node {
int ch[2], tag, col, minv[2], maxv[2], p[2];
}t[N];
int isout(int x1,int y1,int x2,int y2,int x) {
return (x1>t[x].maxv[0]||x2<t[x].minv[0]||y1>t[x].maxv[1]||y2<t[x].minv[1]);
}
int isin(int x1,int y1,int x2,int y2,int x) {
return (t[x].minv[0]>=x1&&t[x].maxv[0]<=x2&&t[x].minv[1]>=y1&&t[x].maxv[1]<=y2);
}
bool cmp(Node a,Node b) {
return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
}
void pushup(int x,int y) {
for(int i=0;i<2;++i)
t[x].minv[i]=min(t[x].minv[i],t[y].minv[i]),t[x].maxv[i]=max(t[x].maxv[i],t[y].maxv[i]);
}
void mark(int x,int c) {
t[x].col=t[x].tag=c;
}
void pushdown(int x) {
if(t[x].tag!=-1) {
if(t[x].ch[0]) mark(t[x].ch[0],t[x].tag);
if(t[x].ch[1]) mark(t[x].ch[1],t[x].tag);
t[x].tag=-1;
}
}
int build(int l,int r,int o) {
int mid=(l+r)>>1,i;
d=o, nth_element(t+l,t+mid,t+1+r,cmp);
t[mid].minv[0]=t[mid].maxv[0]=t[mid].p[0];
t[mid].minv[1]=t[mid].maxv[1]=t[mid].p[1];
t[mid].col=1, t[mid].tag=-1;
if(mid>l) t[mid].ch[0]=build(l,mid-1,o^1), pushup(mid, t[mid].ch[0]);
if(r>mid) t[mid].ch[1]=build(mid+1,r,o^1), pushup(mid, t[mid].ch[1]);
return mid;
}
void update(int x1,int y1,int x2,int y2,int c,int x) {
if(!x||isout(x1,y1,x2,y2,x)) return;
if(isin(x1,y1,x2,y2,x)) {
mark(x,c);
return;
}
if(t[x].p[0]>=x1&&t[x].p[0]<=x2&&t[x].p[1]>=y1&&t[x].p[1]<=y2) t[x].col=c;
pushdown(x);
if(t[x].ch[0])
update(x1,y1,x2,y2,c,t[x].ch[0]);
if(t[x].ch[1])
update(x1,y1,x2,y2,c,t[x].ch[1]);
}
int query(int x1,int y1,int x) {
if(!x||isout(x1,y1,x1,y1,x)) return -1;
if(t[x].p[0]==x1&&t[x].p[1]==y1) return t[x].col;
pushdown(x);
return max(query(x1,y1,t[x].ch[0]), query(x1,y1,t[x].ch[1]));
}
int n,edges,tim,fa[N],hd[N],nex[N],to[N],dfn[N],size[N],dep[N];
void addedge(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs(int u) {
dfn[u]=++tim,size[u]=1;
for(int i=hd[u];i;i=nex[i])
dep[to[i]]=dep[u]+1,dfs(to[i]),size[u]+=size[to[i]];
}
void solve() {
edges=0;
memset(hd,0,sizeof(hd));
int i,j;
int Q,C;
scanf("%d%d%d",&n,&C,&Q);
for(i=2;i<=n;++i) scanf("%d",&fa[i]), addedge(fa[i],i);
dfs(1);
for(i=1;i<=n;++i) t[i].p[0]=dfn[i],t[i].p[1]=dep[i],t[i].ch[0]=t[i].ch[1]=0, t[i].tag=-1;
int root=build(1,n,0);
long long lastans=0;
for(i=1;i<=Q;++i) {
int a,l,c;
scanf("%d%d%d",&a,&l,&c);
if(c==0) lastans=(lastans+(long long)i*query(dfn[a], dep[a], root))%1000000007;
else {
update(dfn[a],dep[a],dfn[a]+size[a]-1,dep[a]+l,c,root);
}
}
printf("%lld\n",lastans);
}
int main() {
int T;
// setIO("input");
scanf("%d",&T);
while(T--) solve();
return 0;
}