Description
给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色
Input
第一行一个数T,表示数据组数
接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数
接下来一行n-1个数描述2..n的父节点
接下来q行每行三个数a,l,c
若c为0,表示询问a的颜色
否则将距离a不超过l的a的子节点染成c
Output
设当前是第i个操作,y_i为本次询问的答案(若本次操作是一个修改则y_i为0),令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7
Sample Input
1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0
Sample Output
32
HINT
第1,3,5,7的询问的答案分别为1,3,3,1,所以答案为 1*1+2*0+3*3+4*0+5*3+6*0+7*1=32.
数据范围:
对于100%的数据T<=6,n,m,c<=10^5,
1<=a<=n,0<=l<=n,0<=c<=c
把一个节点映射到平面上，以DFS序位置作为第一关键字，以深度作为第二关键字。
那么一次修改就是对一个矩形内部的点打上懒标记，KD树水水即可。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
#define L T[o].lc
#define R T[o].rc
using namespace std;
const int BufferSize=<<;
const int inf=1e9;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int D,rt,pos[maxn];
struct Node {
int x[],mx[],mn[],setv,c;
int lc,rc,id,fa;
bool operator < (const Node& ths) const {return x[D]<ths.x[D];}
}P[maxn],T[maxn];
int n,c,q,first[maxn],next[maxn],to[maxn],st[maxn],en[maxn],dep[maxn],e,ToT;
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
}
void dfs(int x) {
P[x].x[]=st[x]=++ToT;P[x].x[]=dep[x];P[x].id=x;
ren dep[to[i]]=dep[x]+,dfs(to[i]);
en[x]=ToT;
}
void build(int& o,int l,int r,int c) {
o=;
if(l>r) return;
int mid=l+r>>;o=mid;D=c;
nth_element(P+l,P+mid,P+r+);
T[o]=P[mid];T[o].setv=T[o].c=;pos[P[mid].id]=mid;
build(L,l,mid-,c^);build(R,mid+,r,c^);
T[L].fa=T[R].fa=o;
T[o].mn[]=min(T[o].x[],min(T[L].mn[],T[R].mn[]));
T[o].mn[]=min(T[o].x[],min(T[L].mn[],T[R].mn[]));
T[o].mx[]=max(T[o].x[],max(T[L].mx[],T[R].mx[]));
T[o].mx[]=max(T[o].x[],max(T[L].mx[],T[R].mx[]));
// printf("%d %d %d %d %d\n",T[o].mn[0],T[o].mx[0],T[o].mn[1],T[o].mx[1],o);
}
void set(int o,int val) {if(o) T[o].setv=T[o].c=val;}
void pushdown(int o) {
if(!T[o].setv) return;
set(L,T[o].setv);set(R,T[o].setv);
T[o].setv=;
}
int in(int o,int x1,int x2,int y1,int y2) {return T[o].mn[]>=x1&&T[o].mx[]<=x2&&T[o].mn[]>=y1&&T[o].mx[]<=y2;}
int out(int o,int x1,int x2,int y1,int y2) {return T[o].mn[]>x2||T[o].mx[]<x1||T[o].mn[]>y2||T[o].mx[]<y1;}
void modify(int o,int x1,int x2,int y1,int y2,int val) {
if(!o) return;pushdown(o);
if(in(o,x1,x2,y1,y2)) {set(o,val);return;}
if(out(o,x1,x2,y1,y2)) return;
if(T[o].x[]>=x1&&T[o].x[]<=x2&&T[o].x[]>=y1&&T[o].x[]<=y2) T[o].c=val;
if(!out(L,x1,x2,y1,y2)) modify(L,x1,x2,y1,y2,val);
if(!out(R,x1,x2,y1,y2)) modify(R,x1,x2,y1,y2,val);
}
int S[maxn],top;
void solve() {
n=read();c=read();q=read();
fill(first+,first+n+,);e=ToT=rt=;
rep(i,,n) AddEdge(read(),i);
dfs();build(rt,,n,);
long long res=;
rep(i,,q) {
int x=read(),l=read(),t=read(),ans=;
if(t) modify(rt,st[x],en[x],dep[x],dep[x]+l,t);
else {
int o=pos[x];
while(o!=rt) S[++top]=T[o].fa,o=T[o].fa;
while(top) pushdown(S[top--]);
ans=T[pos[x]].c;
}
(res+=(long long)ans*i)%=;
}
printf("%lld\n",res);
}
int main() {
T[].mn[]=T[].mn[]=inf;
T[].mx[]=T[].mx[]=-inf;
dwn(T,read(),) solve();
return ;
}