[文章目录]
Description
给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色,n,m,c<=10^5,
KD-tree是二叉树，像线段树一样将修改的矩形覆盖的关键点打标记，每次下传即可。
修改颜色复杂度O(√n)，查询复杂度O(logn)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
const ll mod=1000000007;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char f=0,ch=nc();
while(!isdigit(ch)) {if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
if(f) x=-x;
}
int n,m,d,rot,cg[N],head[N],to[N],nxt[N],cnt,dep[N],in[N],out[N],tim;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
struct KD_tree
{
int p[2],mi[2],mx[2],ls,rs,lz,w;
}t[N];
bool operator < (const KD_tree x,const KD_tree y)
{
return x.p[d]==y.p[d] ? x.p[d^1]<y.p[d^1] : x.p[d]<y.p[d];
}
bool cmp(int x,int y) {return t[x]<t[y];}
void dfs(int x)
{
in[x]=++tim;
t[x].p[0]=t[x].mi[0]=t[x].mx[0]=tim;
t[x].p[1]=t[x].mi[1]=t[x].mx[1]=dep[x];
t[x].w=1; t[x].lz=-1; t[x].ls=t[x].rs=0;
for(int i=head[x];i;i=nxt[i])
{
dep[to[i]]=dep[x]+1;
dfs(to[i]);
}
out[x]=tim;
}
void pushup(int p,int k)
{
t[p].mi[0]=min(t[p].mi[0],t[k].mi[0]);
t[p].mx[0]=max(t[p].mx[0],t[k].mx[0]);
t[p].mi[1]=min(t[p].mi[1],t[k].mi[1]);
t[p].mx[1]=max(t[p].mx[1],t[k].mx[1]);
}
void pushdown(int p)
{
if(~t[p].lz)
{
if(t[p].ls) t[t[p].ls].lz=t[t[p].ls].w=t[p].lz;
if(t[p].rs) t[t[p].rs].lz=t[t[p].rs].w=t[p].lz;
t[p].lz=-1;
}
}
int build(int l,int r,int fl)
{
int mid=(l+r)>>1; d=fl;
nth_element(cg+l,cg+mid,cg+r+1,cmp);
if(l<mid) pushup(cg[mid],t[cg[mid]].ls=build(l,mid-1,fl^1));
if(r>mid) pushup(cg[mid],t[cg[mid]].rs=build(mid+1,r,fl^1));
return cg[mid];
}
int query(int p,int x,int fl)
{
if(p==x) return t[p].w;
d=fl; pushdown(p);
if(t[x]<t[p]) return query(t[p].ls,x,fl^1);
else return query(t[p].rs,x,fl^1);
}
void fix(int p,int x,int dx,int y,int dy,int c)
{
if(!p||dx<t[p].mi[0]||x>t[p].mx[0]||dy<t[p].mi[1]||y>t[p].mx[1]) return ;
if(x<=t[p].mi[0]&&dx>=t[p].mx[0]&&y<=t[p].mi[1]&&dy>=t[p].mx[1])
{
t[p].w=t[p].lz=c;
return ;
}
pushdown(p);
if(t[p].p[0]>=x&&t[p].p[0]<=dx&&t[p].p[1]>=y&&t[p].p[1]<=dy) t[p].w=c;
fix(t[p].ls,x,dx,y,dy,c);
fix(t[p].rs,x,dx,y,dy,c);
}
int main()
{
int T; read(T);
while(T--)
{
memset(head,0,sizeof(int)*(n+10)); tim=cnt=0;
int x;
read(n); read(x); read(m);
for(int i=2;i<=n;++i)
{
read(x);
add(x,i);
}
dfs(1);
for(int i=1;i<=n;++i) cg[i]=i;
rot=build(1,n,0);
ll ans=0; int a,l,c;
for(int i=1;i<=m;++i)
{
read(a); read(l); read(c);
if(c==0) ans=(ans+(ll)query(rot,a,0)*i)%mod;
else fix(rot,in[a],out[a],dep[a],dep[a]+l,c);
}
printf("%lld\n",ans);
}
return 0;
}