问题描述

给定一棵 $n$ 个点的有根树,其中 $1$ 号点是根节点。每个节点都被染上了某一种颜色,其中第 $i$ 个节点的颜色为 $c_i$。定义 $depth_i$ 为 $i$ 节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为 $1$。

站在这棵色彩斑斓的树前面,你将面临 $m$ 个问题。每个问题包含两个整数 $x$ 和 $d$,表示询问 $x$ 子树里且 $depth$ 不超过 $depth_x+d$ 的所有点中出现了多少种本质不同的颜色。

输入

第一行包含一个正整数 $T(1<=T<=500)$,表示测试数据的组数。

每组数据中,第一行包含两个正整数 $n$ 和 $m (1 \leq n,m \leq 100000)$,表示节点数和询问数。
第二行包含 $n$ 个正整数,其中第 $i$ 个数为 $c_i(1\leq c_i \leq n)$,分别表示每个节点的颜色。
第三行包含 $n-1$ 个正整数,其中第 $i$ 个数为 $f_{i+1} (1\leq f_i<i)$,表示节点 $i+1$ 的父亲节点的编号。
接下来 $m$ 行,每行两个整数 $x(1\leq x \leq n)$ 和 $d(0 \leq d < n) $,依次表示每个询问。
输入数据经过了加密,对于每个询问,如果你读入了 $x$ 和 $d$,那么真实的 $x$ 和 $d$ 分别是 $x \oplus last$ 和 $d \oplus last$,其中 $last$ 上一次询问的答案。

输入数据保证 $n$ 和 $m$ 的总和不超过 $500000$。

输出

对于每个询问输出一行一个整数,即答案。

思路

方法一:
如果这个问题在序列上且离线的话,可以发现这就是「HH的项链」。其中一个比较好的思路就是先将询问排序,从左到右扫一遍,我们将每种颜色的贡献算在这种颜色最右边的点上,用树状数组维护区间和即可。强制在线怎么办?可持久化一下,每个右端点都建一个线段树即可。

把这个放在树上也是一样,按深度从大到小考虑,我们将每种颜色的贡献算在这种颜色最浅的点上,用一个以深度为下标的线段树计算子树的答案,然后从下到上线段树合并就好。同时再开一个以颜色为下标的线段树维护深度,同样从下向上合并,合并时把较深的一点贡献在计算答案的线段树上删去。强制在线怎么办?将线段树合并的过程可持久化一下就好。空间复杂度似乎是多一个 $\log$ 的。

方法二:
类似的从序列上的问题考虑。还有一种想法就是,从左到右扫一遍,每当加入一个颜色的点时,加上这个点的贡献,并删去这个颜色上一个点的贡献,同样用树状数组维护区间和就好。

如果把这个放在树上,就是按深度从小到大考虑,每增加一个颜色的点时,就加上这个点的贡献,并在它和与它颜色相同且相邻的点的 LCA 上删去贡献(这里的相邻是指 dfs 序上两点之间没有其他相同颜色的点)。因为一棵子树的 DFS 是连续一段,这样就可以按深度从小到大扫,用线段树维护子树区间和即可。强制在线怎么办?可持久化,每个深度都建一个线段树就好。

代码

嘴巴选手,懒,不想写代码

1 对 “BZOJ4771 七彩树 [主席树/线段树合并]”的想法;

发表评论

邮箱地址不会被公开。 必填项已用*标注