P5311 [Ynoi2011] Chengdu No. 7 High School

When I was in middle school, I had heard that Chengdu No. 7 High School was very strong. My grades in regular classes were pretty good at that time, so I also wanted to go there. I do not really remember what I thought about high school back then, but from my vague impressions, I guess I really looked forward to it. In my 9th grade, I found a way to contact Teacher Lin, the contest coach at cdqz, and got permission to sit in on OI lectures on weekends. I still remember the senior student who taught us was “Yu Shen” from the CTT. He started by teaching us data structures. The bright and spacious (as I remembered) computer room at cdqz, and the beamer style that I had never seen before, left a deep impression on me. The first lesson was about the Binary Indexed Tree. I did not understand it at all. Now I feel that it is not suitable as the first topic, because the structure is quite hard to understand. It is also not like a segment tree with a very intuitive divide-and-conquer structure, and the code is highly specialized and very short, which makes it easy to get confused. The second lesson was about the segment tree. I understood part of it and felt it was amazing, but when it got to the “lazy tag” part, I could not understand it anymore. After the lecture we did problems; I wrote a very long and ugly segment tree, debugged for a very long time, and somehow passed the problem while only half understanding it. At that time I was doing problems on vijos. The feeling of seeing “Xiaobai Strolling in the Park” was like AMX-1357 seeing “Mouse Lord”. There were exams every day. During exams I basically knew nothing, so I could only write brute force to get partial points. Every time during judging I saw the seniors solve many problems, and I felt very envious. One person who went to cdqz with me was zms. He got 1st place in the province in the Junior group in 8th grade, and in 9th grade he almost got 1st prize in the Senior group. I always treated him as my competitor. In every exam I compared my score with his, but basically I always lost. [Remember to add pictures: the exam scores at that time (probably cannot find them), the PPT at that time (probably cannot find it), the school gate of Chengdu No. 7 High School (this one exists).] Since this is Ynoi, not a place for the problem setter to write boring text, you need to solve a data structure problem.

You are given a tree with $n$ nodes. Each node has a color. There are $m$ queries. Each query gives parameters $l\ r\ x$. You need to output: Keep all nodes whose indices are in $[l,r]$ in the tree. In the connected component that contains $x$, output the number of distinct colors. Each query is independent.

The first line contains two integers $n,m$. The second line contains $n$ integers representing the color of each node. Then follow $n-1$ lines. Each line contains two integers $x$ and $y$, indicating there is an edge between $x$ and $y$. Then follow $m$ lines. Each line contains three integers $l\ r\ x$, representing one query.

For each query, output one line with one integer, the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: created_equal1, Data: nzhtl1477. Constraints: For $100\%$ of the testdata, all numbers that appear are in $[1,10^5]$, and it is guaranteed that for each query $l \le x \le r$. Translated by ChatGPT 5