我永远喜欢数据结构。
给出 \(n\) 个点的树，点有颜色 \(a_i\)。有 \(q\) 次询问，每次询问给出 \(l,r,x\)，求保留 \([l,r]\) 范围内的节点时，\(x\) 所在联通块中有多少种本质不同的颜色。询问之间相互独立。
不保留一个点的定义是，将这个点以及与其相邻的边全部删除。
\(n,q\le 10^5\)。
\(1.00\,\text{s}\,/\,250.00\,\text{MB}\)。
lxl 难得不卡常。
一句话题解：转化，离线。
记 \((l,r,x)\) 为一个询问，\(S_{x,[l,r]}\) 为 \(x\) 能够通过 \([l,r]\) 内的点走到的点的集合。询问本质上是对 \(S_{x,[l,r]}\) 数颜色。
我们发现若 \(y\in S_{x,[l,r]}\)，则询问 \((l,r,x)\) 等价于 \((l,r,y)\)。因为若 \(x\) 能走到一个点 \(u\)，那么 \(y\) 也可以通过 \(x\) 到达点 \(u\)，反之亦然。其实就是此时 \(S_{x,[l,r]}=S_{y,[l,r]}\)。
考虑点分治，设当前分治重心为 \(rt\)。考虑对于当前子树内部一个点上未被处理的 \((l,r,x)\) 的询问，若 \(rt\in S_{x,[l,r]}\)，则可以考虑求解 \((l,r,rt)\) 的答案。
可以证明对于任意一个点一定存在一个这样的 \(\boldsymbol{rt}\)。
注意到此时 \(\boldsymbol{S_{rt,[l,r]}}\) 中的点全部在当前子树中。
若不在，则 \(x\) 一定和上层分治重心通过 \([l,r]\) 内的点联通，本层就不会再处理这个询问。
于是维护 \(mxe_u\) 和 \(mne_u\) 表示 \(u\) 到 \(rt\) 的路径上最大 / 最小的点。那么对于一个颜色 \(c\)，它对这个答案有贡献，当且仅当存在一个点 \(v\) 使得 \(a_v=c\)，且 \(l\le mne_v\le mxe_v\le r\)。
这是个二维数点问题，考虑将所有询问和 \((mne_v,mxe_v)\) 点对按照第一维从大到小排序，从大到小扫描。扫到一个询问时，上述条件可以转化为当前有多少种颜色的最小 \(mxe_v\) 值不超过 \(r\)。用树状数组维护即可。
一个点在 \(\mathcal{O}(\log n)\) 层分治中，每层扫到一次，单次复杂度为 \(\mathcal{O}(n\log n)\)。一个询问会在 \(\mathcal{O}(\log n)\) 层分治中被扫到，仅会在一层分治中回答，复杂度为 \(\mathcal{O}(\log n)\)。
综上，时间复杂度为 \(\mathcal{O}(n\log^2 n+q\log n)\)，空间复杂度为 \(\mathcal{O}(n+q)\)。
提交记录（\(\color{white}\colorbox{limegreen} {Accepted}\) \(\color{limegreen} \bf 100\)，\(\bf 139\,\text{ms}\,/\,16.94\,\text{MB}\)） 代码
标签：rt,一个点,log,七中,Ynoi2011,询问,分治,mathcal,P5311 From： https://www.cnblogs.com/MnZnOIerLzy/p/17865760.html