【题目】
给定一棵以 1 1 1为根的有根树,初始所有节点颜色为 1 1 1,每次将距离节点 a a a不超过 l l l的 a a a的子节点染成 c c c,或询问点 a a a的颜色。
n ≤ 1 0 5 n\leq 10^5 n≤105
【解题思路】
将 dfs \text{dfs} dfs序作为一维，深度作为一维，直接上 KD \text{KD} KD树即可。
【【KD树】BZOJ 4154 [Ipsc2015]Generating Synergy】【参考代码】
#include
using namespace std;
const int N=1e5+10,mod=1e9+7;
int read()
{
int ret=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
return ret;
}namespace Data_Structure
{
struct coor
{
int x,y;
coor(int _x=0,int _y=0):x(_x),y(_y){}
friend coor gmax(const coor&a,const coor&b){return coor(max(a.x,b.x),max(a.y,b.y));
}
friend coor gmin(const coor&a,const coor&b){return coor(min(a.x,b.x),min(a.y,b.y));
}
}a[N],b[N];
bool cmpx(const coor&a,const coor&b){return a.x>1;
nth_element(b+l,b+mid,b+r+1,D?cmpx:cmpy);
t[x].p=t[x].mx=t[x].mi=b[mid];
t[x].col=1;
t[x].cov=0;
ls=rs=0;
if(lmid) build(rs,mid+1,r,D^1),t[x].mx=gmax(t[x].mx,t[rs].mx),t[x].mi=gmin(t[x].mi,t[rs].mi);
//printf("%d %d %d %d %d %d %d %d %d\n",x,l,r,t[x].p.x,t[x].p.y,t[x].mi.x,t[x].mx.x,t[x].mi.y,t[x].mx.y);
}
int inmp(const coor&l,const coor&r,int xl,int xr,int yl,int yr)
{
if(xl<=l.x && r.x<=xr && yl<=l.y && r.y<=yr) return 1;
if(r.xxr || r.yyr) return -1;
return 0;
}
void pushdown(int x)
{
if(t[x].cov) t[ls].cov=t[rs].cov=t[ls].col=t[rs].col=t[x].cov,t[x].cov=0;
}
void update(int x,int xl,int xr,int yl,int yr,int c)
{
if(!x) return;
pushdown(x);
int v=inmp(t[x].mi,t[x].mx,xl,xr,yl,yr);
//printf("%d %d %d %d %d %d %d %d\n",x,t[x].p.x,t[x].p.y,xl,xr,yl,yr,v);
if(!~v) return;
if(v) {t[x].cov=t[x].col=c;
return;
}
if(inmp(t[x].p,t[x].p,xl,xr,yl,yr)==1) t[x].col=c;
update(ls,xl,xr,yl,yr,c);
update(rs,xl,xr,yl,yr,c);
}
int query(int x,int l,int r)
{
//cerr< 
