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
Solution
将每个点看成二维点$(DFN[x],Depth[x])$，也就是$DFS$序和深度。
这样的话这个题就变成了单点查询和区间打标记覆盖了。
区间打标记的时候记得把路径上经过的点颜色修改一下……因为这里挂了调了好久（
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (100009)
#define MOD (1000000007)
using namespace std; struct Edge{int to,next;}edge[N];
int T,n,c,q,x,a,l,opt,ans,dfs_num,D,MaxDep;
int DFN[N],Depth[N],Size[N];
int head[N],num_edge; struct Node
{
int Max[],Min[],d[],ls,rs,col,cov;
bool operator < (const Node &a) const {return d[D]<a.d[D];}
}p[N],Q; struct KDT
{
Node T[N];
void Pushup(int now)
{
int ls=T[now].ls,rs=T[now].rs;
for (int i=; i<=; ++i)
{
T[now].Max[i]=T[now].Min[i]=T[now].d[i];
if (ls)
{
T[now].Max[i]=max(T[now].Max[i],T[ls].Max[i]);
T[now].Min[i]=min(T[now].Min[i],T[ls].Min[i]);
}
if (rs)
{
T[now].Max[i]=max(T[now].Max[i],T[rs].Max[i]);
T[now].Min[i]=min(T[now].Min[i],T[rs].Min[i]);
}
}
}
void Pushdown(int now)
{
if (T[now].cov!=-)
{
int ls=T[now].ls,rs=T[now].rs;
T[ls].cov=T[ls].col=T[now].cov;
T[rs].cov=T[rs].col=T[now].cov;
T[now].cov=-;
}
}
int Build(int opt,int l,int r)
{
if (l>r) return ;
int mid=(l+r)>>;
D=opt; nth_element(p+l,p+mid,p+r+);
T[mid]=p[mid];
T[mid].ls=Build(opt^,l,mid-);
T[mid].rs=Build(opt^,mid+,r);
Pushup(mid); return mid;
}
int Query(int now)
{
if (Q.d[]<T[now].Min[] || Q.d[]>T[now].Max[]) return ;
if (Q.d[]<T[now].Min[] || Q.d[]>T[now].Max[]) return ;
if (Q.d[]==T[now].d[] && Q.d[]==T[now].d[]) return T[now].col;
Pushdown(now); return Query(T[now].ls)+Query(T[now].rs);
}
void Update(int now,int k)
{
if (Q.Min[]>T[now].Max[] || Q.Max[]<T[now].Min[] || Q.Min[]>T[now].Max[] || Q.Max[]<T[now].Min[]) return;
if (Q.Min[]<=T[now].Min[] && Q.Max[]>=T[now].Max[] && Q.Min[]<=T[now].Min[] && Q.Max[]>=T[now].Max[])
{
T[now].col=k; T[now].cov=k;
return;
}
Pushdown(now);
if (T[now].d[]>=Q.Min[] && T[now].d[]<=Q.Max[] && T[now].d[]>=Q.Min[] && T[now].d[]<=Q.Max[])
T[now].col=k;
Update(T[now].ls,k); Update(T[now].rs,k);
}
}KDT; inline int read()
{
int x=; char c=getchar();
while (c<'' || c>'') c=getchar();
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x;
} void add(int u,int v)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
head[u]=num_edge;
} void DFS(int x)
{
Size[x]=; DFN[x]=++dfs_num;
for (int i=head[x]; i; i=edge[i].next)
{
Depth[edge[i].to]=Depth[x]+;
DFS(edge[i].to);
Size[x]+=Size[edge[i].to];
}
MaxDep=max(MaxDep,Depth[x]);
} int main()
{
T=read();
while (T--)
{
memset(head,,sizeof(head));
memset(Depth,,sizeof(Depth));
num_edge=dfs_num=MaxDep=ans=;
n=read(); c=read(); q=read();
for (int i=; i<=n; ++i)
p[i].col=, p[i].cov=-;
for (int i=; i<=n; ++i)
x=read(), add(x,i);
DFS();
for (int i=; i<=n; ++i)
p[i].d[]=DFN[i], p[i].d[]=Depth[i];
int Root=KDT.Build(,,n);
for (int i=; i<=q; ++i)
{
a=read(); l=read(); opt=read();
if (opt==)
{
Q.d[]=DFN[a]; Q.d[]=Depth[a];
(ans+=1ll*i*KDT.Query(Root)%MOD)%=MOD;
}
else
{
Q.Min[]=DFN[a]; Q.Max[]=DFN[a]+Size[a]-;
Q.Min[]=Depth[a]; Q.Max[]=min(MaxDep,Depth[a]+l);
KDT.Update(Root,opt);
}
}
printf("%d\n",ans);
}
}