P15533 【MYCOI R1】The Tree of Friendship

In Xiao Che and Xiao Meng's school, there are $n$ students. They are divided into two types: introverted and extroverted. There are some friendships among the students. Define $u \leftrightarrow v$ to mean that student $u$ and student $v$ are good friends. For two students $x, y$, if there exists a sequence of students $a_1 = x, a_2, \ldots, a_k = y$ such that $a_1 \leftrightarrow a_2$, $a_2 \leftrightarrow a_3$, $\ldots$, $a_{k-1} \leftrightarrow a_k$, then $k-1$ is called a "spacing" between $x$ and $y$. The "friend distance" $d(x, y)$ is defined as the minimum "spacing" between $x$ and $y$. Thus, the "friend distance" between good friends is $1$. Upon entering school (the morning of the first day), the $n$ students, for various reasons, have formed $n-1$ pairs of good friends, and there exists a "friend distance" between any two students. In other words, if we regard the students as nodes on a tree and the good friend relationships as edges between nodes, the initial relationships among the $n$ students form a tree. The students enjoy making friends. Each day, for any three students $a, b, c$, if $a$ and $b$ are both "extroverted", and on the morning of that day $a$ and $b$ are good friends, and $b$ and $c$ are good friends, then at noon that day $a$ and $c$ will become good friends (**note that $c$ can be "introverted"**). As a result, the "friend distance" between students will gradually decrease. However, as time goes on, the pressure of academic courses increases, and students spend more time studying rather than socializing. Therefore, on the evening of day $t$, the "social cost" between $x$ and $y$ is $d(x, y) + t$. Xiao Che and Xiao Meng want to know, if they are students $u$ and $v$, what is the minimum "social cost" among the $T$ evenings from day $1$ to day $T$?

The first line contains two positive integers $n, q$, representing the number of students and the number of queries. The second line contains $n$ characters. The $i$-th character represents the personality of student $i$ (`I` for introverted, `E` for extroverted). The next $n-1$ lines each contain two positive integers $u, v$, indicating that $u$ and $v$ are good friends on the morning of the first day. The last $q$ lines each contain three positive integers $u, v, T$, as described above.

For each query, output a line containing a positive integer representing the answer.

**This problem uses bundled testing.** ::cute-table{tuack} | Subtask | Special Properties | Points | |:-------:|:-----------------:|:------:| | Subtask 1 | $n, q, T \le 1145$ | 30 | | Subtask 2 | Initially, exactly $2$ students have exactly $1$ good friend, and the remaining $n-2$ students have exactly $2$ good friends. | 5 | | Subtask 3 | Initially, there exists a student who has $n-1$ "good friends". | 10 | | Subtask 4 | All students are extroverted. | 15 | | Subtask 5 | $T \le 1$ | 15 | | Subtask 6 | No special properties | 25 | For $100\%$ of the data: $3 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le u, v \le n$, $1 \le T \le 10^5$.