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
Sample Output
32
Solution
(kd\_tree)。
每个点看做二维平面上的((dfn[x],dep[x]))，然后用支持区间修改的(kd\_tree)就行了。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 2e5+10;
int dfn[maxn],dep[maxn],n,c,q,sz[maxn],id[maxn];
struct Input_Tree {
int head[maxn],tot,dfn_cnt;
struct edge{int to,nxt;}e[maxn<<1];
void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
void ins(int u,int v) {add(u,v),add(v,u);}
void dfs(int x,int fa) {
dep[x]=dep[fa]+1,dfn[x]=++dfn_cnt,sz[x]=1;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to];
}
}T;
struct data {
int l,r,d[2],mx[2],mn[2],col,tag,f;
void clear() {l=r=d[0]=d[1]=0,mn[0]=mn[1]=mx[0]=mx[1]=0,col=tag=0;}
}t[maxn];
int Dem,u,d,L,R,cst;
int cmp(data a,data b) {return a.d[Dem]<b.d[Dem];}
inline void chmin(int &x,int y) {if(y<x) x=y;}
inline void chmax(int &x,int y) {if(y>x) x=y;}
struct kd_tree {
int rt;
void up(int x) {
int l=t[x].l,r=t[x].r;
if(l) {
chmin(t[x].mn[0],t[l].mn[0]);
chmin(t[x].mn[1],t[l].mn[1]);
chmax(t[x].mx[0],t[l].mx[0]);
chmax(t[x].mx[1],t[l].mx[1]);
}
if(r) {
chmin(t[x].mn[0],t[r].mn[0]);
chmin(t[x].mn[1],t[r].mn[1]);
chmax(t[x].mx[0],t[r].mx[0]);
chmax(t[x].mx[1],t[r].mx[1]);
}
}
int build(int l,int r,int D,int fa) {
int mid=(l+r)>>1;
Dem=D;nth_element(t+l+1,t+mid+1,t+r+1,cmp);
t[mid].mx[0]=t[mid].mn[0]=t[mid].d[0];t[mid].f=fa;
t[mid].mx[1]=t[mid].mn[1]=t[mid].d[1];
if(l!=mid) t[mid].l=build(l,mid-1,D^1,mid);
if(r!=mid) t[mid].r=build(mid+1,r,D^1,mid);
t[mid].col=1;id[t[mid].tag]=mid;t[mid].tag=0;
up(mid);
return mid;
}
void push_tag(int p,int r) {t[p].col=t[p].tag=r;}
void pushdown(int p) {
if(!t[p].tag) return ;
if(t[p].l) push_tag(t[p].l,t[p].tag);
if(t[p].r) push_tag(t[p].r,t[p].tag);
t[p].tag=0;
}
void modify(int p) {
if(t[p].mn[0]>R||t[p].mx[0]<L||t[p].mn[1]>u||t[p].mx[1]<d) return ;
if(t[p].mn[0]>=L&&t[p].mx[0]<=R&&t[p].mn[1]>=d&&t[p].mx[1]<=u) return push_tag(p,cst),void();
pushdown(p);
if(L<=t[p].d[0]&&t[p].d[0]<=R&&d<=t[p].d[1]&&t[p].d[1]<=u) t[p].col=cst;
if(t[p].l) modify(t[p].l);
if(t[p].r) modify(t[p].r);
}
int sta[maxn],top;
int query(int x) {
int a=x;
while(t[x].f) sta[++top]=t[x].f,x=t[x].f;
while(top) pushdown(sta[top--]);
return t[a].col;
}
}kdt;
const int mod = 1e9+7;
void clear() {
for(int i=1;i<=n;i++) t[i].clear(),T.head[i]=dep[i]=dfn[i]=sz[i]=0;
T.tot=T.dfn_cnt=0;
}
void solve() {
read(n),read(c),read(q);
for(int i=2,x;i<=n;i++) read(x),T.ins(i,x);
T.dfs(1,0);
for(int i=1;i<=n;i++) t[i].d[0]=dfn[i],t[i].d[1]=dep[i],t[i].tag=i;
kdt.rt=kdt.build(1,n,0,0);int ans=0;
for(int i=1;i<=q;i++) {
int a,l,cc;read(a),read(l),read(cc);
if(!cc) ans=(0ll+ans+1ll*i*kdt.query(id[a]))%mod;
else L=dfn[a],R=dfn[a]+sz[a]-1,u=dep[a]+l,d=dep[a],cst=cc,kdt.modify(kdt.rt);
}
write(ans);
}
int main() {
int ttt;read(ttt);while(ttt--) clear(),solve();
return 0;
}