P6580 [Ynoi2019] A Wonderful Every Day~ The Existence of Discontinuity

3.0321. Although “outside” can represent, in space, a situation that breaks the laws of physics. But “outside” cannot represent, in space, a situation that breaks the laws of geometry. Ludwig Josef Johann Wittgenstein, *Tractatus Logico-Philosophicus*.  …… Transparent… Transparent white? …No… no, that’s not it. This isn’t some kind of transparent white… If it’s white, then it can’t be transparent…… then… this is translucent… But… this… is not translucent either… If… I have to find the only word that can express it… Then it is… Transparent white… This is… that thing… this is… “Light”. 【Light】 Light? This is pure light. Yes…… that’s it…… This is— —light. The sound of cicadas…… This is… the rooftop? Looking around… that is a common sight… the rooftop of Building A. Why… why am I here… Mamaya Minamori jumped down to protect Usaki… and then…, and then…, then what happened? What day is it today? Um, right now it is… I checked my watch, and the date was July 20, 2012. From then… a whole day… What on earth happened… A dream…… they say that even lucid dreams rarely let you feel pain…… If pinching my cheek hurts, does that mean this scenery is reality…… Otonashi Ayana… classmate. “Long time no see.” “What’s wrong?” Because… it’s only been one day since the last time we met, right? “…I see.” …I said. “What?” How is Mamaya Minamori? “Why… ask something like that?” W-well of course it’s because I’m worried… and anyway I’m just a personality he created… “Then doesn’t that mean he’s still alive?” What… did you say? “Hypothesis 1… if you… are one of the personalities created by Mamaya Minamori, then the fact that you exist itself is the reason his body still exists…” B-but… that’s strange, right? “What’s strange?” Because… he was so badly injured. How could he come to a place like this after just one day? “I see…” If I appeared, it should be on a hospital bed. “Then Hypothesis 2… your existence is not caused by dissociative identity disorder…” “Your existence is the soul of a person who truly existed in the past, Mizukami Yuki. If this soul is dwelling in Mamaya Minamori… then the reason you exist here, in other words…” “It means Mamaya Minamori’s death…” N-no way… “And Hypothesis 3… if this is only a dream you are having…” “The me in front of you… is also just a product of the dream… this hypothesis is quite convincing…” “Then… Mizukami Yuki, which of these do you prefer as an explanation of the current situation?” Which do I prefer… I don’t think that’s the point… “Hypothesis 4… you are just a hallucination I’m seeing… an illusion I created… meaning you do not exist.” Ahahaha… then what am I, who is thinking right now? Isn’t there a me that is thinking right now? “It’s just that I’m recognizing part of my brain activity… as a different personality…” “In other words, the fact that ‘you are thinking’ cannot prove that you exist…” “It cannot deny the possibility at all that the Mizukami Yuki who exists here right now… is another personality created by me.” “You, who created three personalities in one body, should understand this best…” “The fact that you are thinking… cannot become proof that you exist…” What I want to know is… “What?” So, what happened after that? “If you want to know, then check it yourself… open the rooftop door and run out into the outside world… All you need to do is that, and only that.”  … Just as Ayana said. If I really cared that much… I just had to leave here. Run away from this rooftop and go look at the outside world. If I do that, I should be able to get what I want… and know the outcome of everything. But… I just need to go outside…? “Yes.” This is one way… but can I ask a question? “What?” What day is it today? “July 20, 2012…” So… starting tomorrow it’s summer vacation? “Yes… starting tomorrow it’s summer vacation…” Yesterday… there should have been a mass suicide. It’s not something trivial where you can calmly go on summer vacation as usual. And yet… the scenery seen from the rooftop… is the same ordinary daily life as always… Students walking in the hallway. Students talking in the classroom. A teacher calling students to come over. An everyday life with no changes. It really doesn’t look like such an incident just happened… “What’s wrong?” …Are those the only hypotheses you have, Ayana? “Hypotheses… do you want more?” “As many explanations as you want… annotations for this world… people can add as many as they want.” “If that is your wish… no matter how many…” What is the “End Sky” that Takashi-kun talked about? That… is a word that doesn’t appear in either Kotomi’s prophecy or the Byakurenka Association’s prophecy… “End Sky… literally means ‘the sky of the end’.” That name… who came up with it, and when? “Memory…” Memory? “Ghost Room… End Sky…” Uh. “Hehe… you remember.” It’s not that I remember… I must have remembered it wrong… “Is that so?” B-because, um… that’s strange, right? “What’s strange?” Because… um… wasn’t that a dream I had when I got caught up in Takashima’s suicide? So isn’t it strange? “What’s strange about it?” Because… if that was after I had already been caught up in Takashima’s suicide… then the timeline is completely messed up… because after that I experienced Takashima’s suicide once again. “Hypothesis 5… up to now, you still haven’t woken up from that dream…” That dream? “Mizukami Yuki who was caught up in Takashima Zakuro’s suicide… this present moment is the continuation of her dream.” A d-dream? Now? N-no… but no matter how I think about it, calling this a dream is too… “Is that so… then Hypothesis 6… the memories of ‘Ghost Room… End Sky’ are false memories…” “It’s just that the confusion of memories caused by repeated personality switching made you have such a dream…” “Takashima Zakuro who jumped did not hit Mizukami Yuki; it was simply memory confusion.” T-then why would Takashi-kun use the word “End Sky” that only appeared in my dream! “Because the two share one brain, there is nothing mysterious about it…” T-then… “Do you care about the scenery you saw at the end… the existence of that sky?” … That sky… seen at the very end… The kind of scenery Takashi Mamaya-kun saw at the instant he jumped. For some reason I felt that scenery was familiar… “A world repeating endlessly… starting from some point…” Uh. “Can you confirm something?” W-what? “May I address you as Mizukami Yuki… classmate?” W-why ask that now… haven’t you been calling me that all along… “Yuki… who is Mizukami Yuki?” Huh? “Yuki is a person who truly existed in the past, died to save Mamaya Usaki… and after that, exists as a personality produced by Mamaya Minamori…” “If so… who is the Yuki who exists here now? Is she the Yuki who is already dead? Or is she the Yuki who is a personality created by Mamaya Minamori?” E-even if you ask me that… I don’t know… “Because you don’t know… that’s why I ask you…” “The final annotation…” “A question to Yuki…” “How many Yukis exist in this world?” Huh? “One is Mizukami Yuki who was born in Saei Village… and died in Saei Village. Another is Mizukami Yuki as a personality created by Mamaya Minamori… and the Mizukami Yuki who exists here now, talking to me.” “Then listen carefully… which number Mizukami Yuki are you?” H-how would I know… and I’m me, there aren’t that many of me. “The Yuki who died in Saei Village, the Yuki inside Minamori, and the Yuki here right now are the same…” “Then what about other possible Yukis?” Other possible me? “Yes… Yuki produced by other personalities… is that also Yuki?” How would I know… besides, if there were that many of me I couldn’t stand it. “But in fact, you are not alone…” “Yuki who was caught up in Takashima Zakuro’s suicide, Yuki who died in Saei Village, Yuki made by Minamori… and Yuki who exists here now…” I-I don’t care about that… I’m me… “In ‘Ghost Room… End Sky’, the scenery you saw… when was that scenery from?” Scenery? Uh. At this moment, for some reason… I remembered the expiration date printed on the chips bag in that amusement ride… I remembered the date on the calendar hanging there… Even though I had no idea what it was… For some reason… I remembered what happened back then. Even though I didn’t know whether that sentence had any meaning. Still, I remembered that date… “The last added annotation.” “Hypothesis 7… all existence is produced by a single soul…”  How far does the sky extend... Probably, it is connected to the sky of the whole world... If so... then this sky and— —End Sky are not connected. If you ask why, that is because, that is something that must not exist— But— is that really true? “————” A voice calling me came from somewhere. The voice of my classmate calling me…… So I turned around…… 

Otonashi Ayana gives you an array $A$, and a tree with $n$ nodes. Each node has a color, which is an integer from $1$ to $x$. There are $m$ queries. For each query, only the nodes in $[l,r]$ are kept on the tree. For a maximal connected component, let $t$ be the number of colors that appear an odd number of times in it. Then its contribution to the answer is $A_t$. That is, the answer is the sum of contributions of all connected components. Queries are independent of each other.

The first line contains three integers $n, m, x$ separated by spaces. The second line contains $n$ integers representing the color of each node. The next $n - 1$ lines each contain two integers $x, y$ separated by spaces, indicating an edge. Then one line contains $x + 1$ integers representing $A_0$ to $A_x$. Then $m$ lines follow, each containing two integers $l, r$ separated by spaces, representing one query.

Output $m$ lines. Each line contains one integer, the answer to this query.

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477. Note: This problem uses **bundled tests**. Only after you pass all test points in a subtask can you get the score for that subtask. For $1\%$ of the testdata, it is Sample 1. For another $9\%$ of the testdata, $n, m \leq 200$. For another $19\%$ of the testdata, $n, m \leq 2000$. For another $19\%$ of the testdata, $x \leq 10$. For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $1 \leq x, A_i \leq 10^4$. Translated by ChatGPT 5