听同学说这题卡空间。

同学指出

void dfs(int now,int fa)
{
	rt[now]=++cnt;dep[now]=dep[fa]+1;
	add(rt[now],1,n,dep[now]);
	for(int i=head[now];i;i=k[i].next)
	{
		if(k[i].to==fa)continue;
		dfs(k[i].to,now);
		rt[now]=merge(rt[now],rt[k[i].to],1,n,k[i].val);
	}
	for(int i=0;i<(int)v[now].size();i++)ans[v[now][i].second]=tr[que(rt[now],1,n,v[now][i].first+dep[now])].sum;
}

这样的话是错误的，因为 $add$ 放在最前面如果是一条链子，空间会被卡成 $n\log n$。

只有改成这样才是对的

void dfs(int now,int fa)
{
	rt[now]=++cnt;dep[now]=dep[fa]+1;
	for(int i=head[now];i;i=k[i].next)
	{
		if(k[i].to==fa)continue;
		dfs(k[i].to,now);
		rt[now]=merge(rt[now],rt[k[i].to],1,n,k[i].val);
	}
	add(rt[now],1,n,dep[now]);
	for(int i=0;i<(int)v[now].size();i++)ans[v[now][i].second]=tr[que(rt[now],1,n,v[now][i].first+dep[now])].sum;
}

但是我惊讶的发现，本来我的做法是 $MLE$ 的，但是改成第二种后开始 $RE$ 了， 这能不能说明我使用了第二种方法后占用的数组更多了？

有没有大佬能教教我如何优化空间。

我的写法有些 sb ，和题解区的线段树合并不太一样，占用的空间会更大。

代码放在二楼