bzoj-4154

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色

第一行一个数T,表示数据组数 接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数 接下来一行n-1个数描述2..n的父节点 接下来q行每行三个数a,l,c 若c为0,表示询问a的颜色 否则将距离a不超过l的a的子节点染成c

设当前是第i个操作,y_i为本次询问的答案(若本次操作是一个修改则y_i为0),令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7

蒟蒻不会kdtree，写的树套树，除了样例全挂/kk

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+7,mod=1e9+7;
vector<int> g[MAXN];
struct node{
	int col,tim,ls,rs;
}tree[MAXN*400];
struct tag{
	int l,r,col,tim;
	void clear()
	{
		l=r=col=tim=0;
		return ;
	}
}lazy[MAXN<<3];
int dfn[MAXN],dep[MAXN],size[MAXN],rt[MAXN<<3],maxdep,tot,sum;
pair<int,int> ask(int p,int l,int r,int x)
{
	if(!p)
		return make_pair(1,0);
	if(l==r)
		return make_pair(tree[p].col,tree[p].tim);
	int mid=(l+r)>>1;
	pair<int,int> ans;
	if(x<=mid)
		ans=ask(tree[p].ls,l,mid,x);
	else
		ans=ask(tree[p].rs,mid+1,r,x);
	if(tree[p].tim>ans.second)
		ans=make_pair(tree[p].col,tree[p].tim);
	return ans;
}
void modify(int &p,int l,int r,int x,int y,int v,int t)
{
	if(!p)
		return ;
	if(tree[p].tim>t)
		return ;
	if(x<=l&&r<=y)
	{
		if(tree[p].tim<t)
		{
			tree[p].col=v;
			tree[p].tim=t;
		}
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		modify(tree[p].ls,l,mid,x,y,v,t);
	if(mid<y)
		modify(tree[p].rs,mid+1,r,x,y,v,t);
	return ;
}
void pushdown(int p,int l,int r,int mid)
{
	if(lazy[p*2].tim<lazy[p].tim)
		lazy[p*2]=lazy[p];
	if(lazy[p*2+1].tim<lazy[p].tim)
		lazy[p*2+1]=lazy[p];
	if(l==mid||mid+1==r)
	{
		modify(rt[p*2],1,maxdep,lazy[p].l,lazy[p].r,lazy[p].col,lazy[p].tim);
		modify(rt[p*2+1],1,maxdep,lazy[p].l,lazy[p].r,lazy[p].col,lazy[p].tim);
	}
	lazy[p].clear();
	return ;
}
int query(int p,int l,int r,int x,int y)
{
	if(l==r)
		return ask(rt[p],1,maxdep,y).first;
	int mid=(l+r)>>1;
	if(lazy[p].col)
		pushdown(p,l,r,mid);
	if(x<=mid)
		return query(p*2,l,mid,x,y);
	else
		return query(p*2+1,mid+1,r,x,y);
}
void change(int p,int l,int r,int x,int y,int ql,int qr,int v)
{
	if(x<=l&&r<=y)
	{
		if(l==r)
			modify(rt[p],1,maxdep,ql,qr,v,tot);
		else
		{
			if(tot>lazy[p].tim)
			{
				lazy[p].l=ql;
				lazy[p].r=qr;
				lazy[p].col=v;
				lazy[p].tim=tot;
			}
		}
		return ;
	}
	int mid=(l+r)>>1;
	if(lazy[p].col)
		pushdown(p,l,r,mid);
	if(x<=mid)
		change(p*2,l,mid,x,y,ql,qr,v);
	if(mid<y)
		change(p*2+1,mid+1,r,x,y,ql,qr,v);
	return ;
}
void build(int &p,int l,int r,int x)
{
	if(!p)
		p=++tot;
	tree[p].col=1;
	tree[p].tim=0;
	tree[p].ls=tree[p].rs=0;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	if(x<=mid)
		build(tree[p].ls,l,mid,x);
	else
		build(tree[p].rs,mid+1,r,x);
	return ;
}
void add(int p,int l,int r,int x,int y)
{
	rt[p]=0;
	if(l==r)
	{
		build(rt[p],1,maxdep,y);
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		add(p*2,l,mid,x,y);
	else
		add(p*2+1,mid+1,r,x,y);
	return ;
}
void dfs(int x,int from)
{
	dep[x]=dep[from]+1;
	size[x]++;
	dfn[x]=++tot;
	for(int i(0);i<g[x].size();++i)
	{
		dfs(g[x][i],x);
		size[x]+=size[g[x][i]];
	}
	return ;
}
signed main()
{
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		int n,c,q;
		scanf("%lld%lld%lld",&n,&c,&q);
		tot=0;
		sum=0;
		for(int i(1);i<=n;++i)
			g[i].clear(),size[i]=0,dep[i]=0;
		for(int i(2);i<=n;++i)
		{
			int fa;
			scanf("%lld",&fa);
			g[fa].push_back(i);
		}
		dfs(1,0);
		maxdep=*max_element(dep+1,dep+n+1);
		tot=0;
		for(int i(1);i<=n;++i)
			add(1,1,n,dfn[i],dep[i]);
		tot=0;
		for(int i(1);i<=q;++i)
		{
			tot++;
			int a,l,opt;
			scanf("%lld%lld%lld",&a,&l,&opt);
			if(opt)
				change(1,1,n,dfn[a],dfn[a]+size[a]-1,dep[a],dep[a]+l,opt);
			else
			{
				printf("%lld %lld\n",query(1,1,n,dfn[a],dep[a]),i);
				sum=(sum+i*query(1,1,n,dfn[a],dep[a])%mod)%mod;
			}
		}
		printf("%lld\n",sum);
	}
	return 0;
}