Description
给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色
区间修改单点查询kdtree
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#define LL long long
using namespace std;
const int P=1e9+7;
const int M=100005;
struct vv{ int c,l,r,mx[2],mn[2],d[2],tag,D; } t[M];
int n,m,k,a[M],C,D,X1,Y1,X2,Y2,x,y,z;
int dfn[M],s[M],dp[M],f[M],T,root;
int ver[M],edge[M],nex[M],head[M],cnt,res;
void add(int x,int y)
{
ver[++cnt]=y, nex[cnt]=head[x], head[x]=cnt;
}
void dfs(int x)
{
dfn[x]=++cnt; dp[x]=dp[f[x]]+1; s[x]=1;
for(int i=head[x];i;i=nex[i]) dfs(ver[i]), s[x]+=s[ver[i]];
}
bool cmp(vv a,vv b)
{
return a.d[D]==b.d[D]?a.d[!D]<b.d[!D] : a.d[D]<b.d[D];
}
void update(int now)
{
if(t[now].l)
{
t[now].mn[0]=min(t[now].mn[0], t[t[now].l].mn[0]);
t[now].mn[1]=min(t[now].mn[1], t[t[now].l].mn[1]);
t[now].mx[0]=max(t[now].mx[0], t[t[now].l].mx[0]);
t[now].mx[1]=max(t[now].mx[1], t[t[now].l].mx[1]);
}
if(t[now].r)
{
t[now].mn[0]=min(t[now].mn[0], t[t[now].r].mn[0]);
t[now].mn[1]=min(t[now].mn[1], t[t[now].r].mn[1]);
t[now].mx[0]=max(t[now].mx[0], t[t[now].r].mx[0]);
t[now].mx[1]=max(t[now].mx[1], t[t[now].r].mx[1]);
}
}
void pd(int now)
{
if(!t[now].tag) return ;
if(t[now].l) t[t[now].l].tag=t[t[now].l].c=t[now].tag;
if(t[now].r) t[t[now].r].tag=t[t[now].r].c=t[now].tag;
t[now].tag=0;
}
int built(int l,int r,int d)
{
D=rand()&1; int mid=(l+r)>>1;
nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].tag=0; t[mid].c=1; t[mid].l=t[mid].r=0; t[mid].D=D;
if(l<mid) t[mid].l=built(l,mid-1,!d);
if(mid<r) t[mid].r=built(mid+1,r,!d);
update(mid);
return mid;
}
void mody(int now,int c)
{
if(X1<=t[now].mn[0] && X2>=t[now].mx[0] && Y1<=t[now].mn[1] && Y2>=t[now].mx[1])
{
t[now].tag=t[now].c=c; return ;
}
if(X1>t[now].mx[0] || X2<t[now].mn[0] || Y1>t[now].mx[0] || Y2<t[now].mn[1]) return;
pd(now);
if(t[now].d[0]>=X1 && t[now].d[0]<=X2 && t[now].d[1]>=Y1 && t[now].d[1]<=Y2) t[now].c=c;
if(t[now].l) mody(t[now].l,c);
if(t[now].r) mody(t[now].r,c);
}
int ask(int now,int x,int y,int d)
{
if(t[now].tag) return t[now].tag; d=t[now].D;
if(t[now].d[0]==x && t[now].d[1]==y) return t[now].c;
if(!d)
{
if(x<t[now].d[0] || (x==t[now].d[0] && y<t[now].d[1])) return ask(t[now].l,x,y,!d);
else return ask(t[now].r,x,y,!d);
}
else
{
if(y<t[now].d[1] || (y==t[now].d[1] && x<t[now].d[0])) return ask(t[now].l,x,y,!d);
else return ask(t[now].r,x,y,!d);
}
}
int main()
{
srand(time(0));
scanf("%d",&T);
for(;T;T--)
{
memset(nex,0,sizeof(nex));
memset(head,0,sizeof(head));
cnt=0;
scanf("%d%d%d",&n,&C,&m);
for(int i=2;i<=n;i++)
{
scanf("%d",&f[i]);
add(f[i],i);
}
dp[1]=1;cnt=0; dfs(1);
for(int i=1;i<=n;i++)
{
t[i].d[0]=t[i].mx[0]=t[i].mn[0]=dfn[i];
t[i].d[1]=t[i].mx[1]=t[i].mn[1]=dp[i];
}
root=built(1,n,0);
LL res=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(!z) res=(res+1ll*i*ask(root,dfn[x],dp[x],0))%P;
else
{
X1=dfn[x], X2=dfn[x]+s[x]-1, Y1=dp[x], Y2=dp[x]+y;
mody(root,z);
}
}
printf("%lld\n",res);
}
}