题目描述给你一棵\(n\)个节点的树，每个节点有一种颜色，有\(m\)次查询操作。查询操作给定参数\(l\r\x\)，需输出：将树中编号在\([l,r]\)内的所有节点保留，\(x\)所在连通块中颜色种类数。每次查询操作独立。对于\(100\%\)的数据，所有出现过的数在\([1,10^5]\)之间，保证每

P5311Ynoi2011成都七中点分树好题，太妙了。思路看到树和连通块，考虑点分树。但是从这里发现原树和点分树的联系实在太小，貌似不可做。可以发现对于一个询问，一个点如果和\(x\)在一个连通块内，那么这个点到\(x\)的最大最小节点编号肯定都在\([l,r]\)这个范围内。可以证明，

洛谷传送门转化一下题意，变成求\(x\)在只经过编号\(\in[l,r]\)的点，能走到多少种颜色。考虑建出点分树。一个结论是原树上的一个连通块，一定存在一个点，使得它在点分树上的子树完全包含这个连通块的所有点。证明考虑点分治的过程，一个连通块如果没被其中一个点剖开就一定在同一

我永远喜欢数据结构。题目传送门给出\(n\)个点的树，点有颜色\(a_i\)。有\(q\)次询问，每次询问给出\(l,r,x\)，求保留\([l,r]\)范围内的节点时，\(x\)所在联通块中有多少种本质不同的颜色。询问之间相互独立。不保留一个点的定义是，将这个点以及与其相邻的边全部删除。