P4679 [ZJOI2011] Gym Battle

In Pokémon (also known as Pocket Monsters), in the Water-type Gym in Red/Blue/Green/Emerald, you need to pass through three ice floors to reach the Gym Leader. Each ice block on an ice floor can be stepped on at most once. Only after all ice blocks on the current ice floor have been stepped on will the stairs to the next ice floor open. The three ice floors are as follows:  After leaving the third ice floor, you can battle the Gym Leader. The Gym Leader thinks this is too easy and many challengers can pass, so to increase the difficulty, the Gym is divided into $n$ rooms. Between any two rooms there is exactly one path, i.e. these $n$ rooms form a tree structure. Each room is divided into two areas, $A$ and $B$. Each area is either a thin ice block or an obstacle. Each move can only go to the same type of area in an adjacent room (that is, if you are currently in area $A$ of this room, then you can only move to area $A$ of an adjacent room), or to the other area of the same room. Now a challenger starts from room $u$, and the Gym Leader is in room $v$. Then the challenger can only move in the direction that gets closer to the room where the Gym Leader is. At the beginning, the challenger may start on either ice area in room $u$. If the number of ice blocks the challenger has stepped on reaches the maximum possible (i.e. there is no strategy that steps on more ice blocks), then when the challenger steps on the last ice block, he will be instantly teleported to the Gym Leader to start the battle. Since the Gym Leader changed the rules, $m$ days have passed. Each day, either a challenger comes to challenge, or the Gym Leader modifies a certain room. For each challenger, you need to compute how many ice blocks he needs to step on in order to battle the Gym Leader.

The first line contains two positive integers $n$ and $m$. Lines $2$ to $n$ each contain two positive integers $x$ and $y$, indicating an edge connecting room $x$ and room $y$. Rooms are numbered $1\cdots n$. Next follow $n$ lines, each containing two characters. Line $n+k$ describes the two areas of room $k$: the first character is area $A$ and the second character is area $B$. Here, “.” (ASCII code 46) means a thin ice block, and “#” (ASCII code 35) means an obstacle. Finally, the next $m$ lines each describe one operation: $C$ $u$ $s$: modify the two areas in room $u$ to $s$. $Q$ $u$ $v$: query the number of ice blocks the challenger needs to step on to battle the Gym Leader, when the challenger is in room $u$ and the Gym Leader is in room $v$. If both areas in room $u$ are obstacles, output $0$.

Output multiple lines, each containing one integer. That is, for each query in the input, output the answer in order.

Constraints: Test points $1$~$6$: $n \le 1000, m \le 10000$. Test points $7$~$15$: $n \le 30000, m \le 80000$. Test points $16$~$20$: $n \le 50000, m \le 100000$. Translated by ChatGPT 5