[Ynoi2011] 成都七中

上初中的时候就听说成都七中非常厉害，我当时文化课成绩还不错，于是也想去成都七中。 当时对高中的看法是什么样的我现在也无从得知了，但从模糊的感觉上大概是很憧憬的。 我初三的时候想办法联系到了cdqz的竞赛教练林老师，然后获得了周末来旁听OI讲课的许可。 还记得讲课的学长是集训队的于神，一开始就在给我们讲数据结构。cdqz明亮宽敞（当时的印象）的机房，和从未见过的beamer排版给我留下了深刻的印象。 第一节课是树状数组，完全没听懂，现在感觉这个东西其实不适合一开始就讲，因为结构理解起来挺麻烦的，也不像线段树那样有一个非常直观的分治结构，而且代码经过特化非常精简，很容易谔谔。 第二节课是线段树，这个听懂了一部分，感觉好神奇，但是讲到标记的部分我就无法理解了，讲完课写题，写了一个很长很丑的线段树，调了很久很久，半懂不懂地把题过了。 当时在做vijos上面的题，看到小白逛公园的感觉就像是AMX-1357看到鼠爷一样。 每天都有考试，考试的时候基本上啥都不会，只能写写暴力分骗分，每次评测的时候都看到学长们过了好多题，当时感觉非常羡慕。 和我一起去cdqz听课的有一位zms，他初二拿了普及组省第一，初三考提高组差点拿了一等奖，我一直以他为竞争对手，每次考试的时候都在和他比划比划成绩，但基本上都是我输。 【记得配图，内容：当时考试的成绩（大概找不到了），当时的PPT（大概找不到了），成都七中校门（这个有）】 由于这是Ynoi，不是出题人拿来写无趣的文字的地方，所以你需要做一个数据结构题：

给你一棵 $n$ 个节点的树，每个节点有一种颜色，有 $m$ 次查询操作。 查询操作给定参数 $l\ r\ x$，需输出： 将树中编号在 $[l,r]$ 内的所有节点保留，$x$ 所在连通块中颜色种类数。 每次查询操作独立。

第一行两个数 $n,m$。 第二行 $n$ 个数表示每个节点的颜色。 之后 $n-1$ 行，每行两个数 $x$ 和 $y$，表示 $x$ 和 $y$ 之间连有一条边。 之后 $m$ 行，每行三个数 $l\ r\ x$，表示一次查询操作。

对每个查询操作，输出一行一个数表示答案。

5 4
1 3 5 3 5
1 2
2 3
3 4
4 5
1 5 1
2 4 3
3 4 3
1 4 3

3
2
2
3

Idea：nzhtl1477，Solution：nzhtl1477，Code：created_equal1，Data：nzhtl1477 对于 $100\%$ 的数据，所有出现过的数在 $[1,10^5]$ 之间，保证每次输入的 $l \le x \le r$。