P5399 [Ynoi2018] A Poor Work

The Pygmalion myth I once read in a book— Back when I was young, I found it very ridiculous. It was the story of a man who devoted himself to carving the woman of his ideals. He would not even glance at real women. He looked down on humans, and only loved inorganic things. He loved something without a soul. At that time, I thought that behavior was extremely foolish. How tragic. Holding high the banner of ideals, he miserably created a projection of love. Self-directed and self-satisfied—that is what losers do. In the end, the man received the pity of the goddess Aphrodite, and the statue was given a soul. The height of shame. It would never be a beautiful tale. With my mood ruined by that stupid story, I roughly threw the book aside. At that moment. I suddenly felt it. A slight uplift, as if the tip of my foot was hanging in the air. A dazzling halo I could not look at directly. A gentle, quiet tightness deep in my heart. For some reason, a gentle feeling spread through my chest. What was this feeling, which I was experiencing for the first time? Warm, sticky, murky. A comfortable nap. The story of a foolish man. A fool’s view of love, with no value in being saved. Realizing that— I—  “No one can understand this kind of trouble at all…” “Wuwu, it hurts so much…” …… “…Huh? Why are you spacing out?” Eh? Ah, no. It’s nothing. Somehow… it feels very similar to me. It is hard because it is a worry I cannot tell anyone. Shu is probably feeling the same way right now. Shu really has hardships that others do not know about. “Ahaha, I guess so.” “Because I have gender identity disorder (xingbie renshi zhang’ai). My body and my inner gender are different, so there’s no one I can share my troubles with.” “For things like this about the lower body, there’s no way I can talk about it with other girls.” That is indeed true… “Ah, I really want to just make my body become female too… what should I do?”  Your body and your inner gender are different… I am not someone with gender identity disorder… But I understand Shu’s feelings very well. “Troubles that neither men nor women can understand… Am I… an incomplete person…?” How could you be incomplete? That’s not true at all. “—Is that so?” …Ah. W-what is it… Just now, Shu’s mood suddenly changed… “—About my troubles, I normally wouldn’t tell anyone.” …… “Because it’s hard to be understood. People treat it as a joke… no one truly wants to help me share the burden.” Th… that is true… And I am the same— “But…” “—I really want to talk it over with you, Yuki-kun…” I already felt close to Shu. A person whose mind and body do not match in gender. Shu has a male body and a female heart. Both Shu and I… in other people’s eyes, we are incomplete beings. But… I— Only I can understand. —Shu is not an incomplete person. Precisely because we are both incomplete, I can fully understand from the bottom of my heart. I… for myself—I want Shu to understand me.  “The five of us will always be friends… In the past… and in the future too…” Amid everyone’s calm voices, I close my eyes. —It will not disappear. Neither the shine of the stars, nor everyone’s warmth. They are already deeply engraved in my heart. I will definitely not forget the days the five of us spent together. No matter what, I will not forget. I will never forget. So that’s it, I was seeking it… Such wonderful bonds… From the bottom of my heart…  Shu’s surprised expression slowly returned to calm. Nervously, I stared at Shu’s lips, not knowing what he would say next. Disgust? Fear? Or would he force out a stiff smile for me? …Any of those would make me sad and miserable. I was very afraid of losing my relationship with Shu. “…Yuki-kun.” My heart was pounding. “I—” The words Shu spoke were only one sentence. “—I can accept you, Yuki-kun.” The words I wanted most— In Shu’s smart style: simple yet perfect words. …Thank you. “Ehehe… you’re welcome.” Shu’s gentle smile embraced me. Being accepted by someone… feels so pleasant. “…Say, Yuki-kun.” “Just like you have an unusual body, I’m not ordinary either.” Shu and I are not the same… “No… I am abnormal too. Because even though I was born as a male, I want to become a girl.” “My body is male… I don’t have breasts, and I don’t have female genitalia. I’m a real male.” “Even so, I still want to become female… I know it. Even though I can’t become one… Even though I know the more I want to become female, the more twisted I will become…” “Even so, I still want to become female. Don’t you think I’m a monster too?” …… I was at a loss for words. But I still only kept silent. At times like this, sugarcoated words will not help. I know casual comfort has no meaning. So… I simply gazed at Shu in silence. “Hehe, Yuki-kun is really gentle… You understand best what I’m thinking.” Because I understand… Shu’s feelings. Hearing me say that, Shu showed a smile from the bottom of his heart. “This is the first time someone has ‘truly’ understood me.” Me too… I finally met someone who could accept me. At the end of a long and hard journey, we finally found salvation. Both Shu and I are far from “ordinary”, and that is why we have suffered so much… But finally we— —met a companion who can understand us.

Caicaizi gives you a tree with $n$ nodes, numbered from $1$ to $n$. Define the distance $d(a,b)$ between two nodes $a,b$ on the tree as the smallest non-negative integer $k$ such that there exists a node sequence $v_0,v_1,...,v_k$ with $v_0=a,v_k=b$, and for $0\leq i\leq k-1$, there is an edge connecting $v_i$ and $v_{i+1}$ in the tree. There are $m$ queries. Each query contains parameters $p_0,d_0,p_1,d_1$. Compute: $$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)$$

The first line contains an integer $n$, representing the number of nodes in the tree. The next line contains $n-1$ integers $f_2,f_3,...,f_n$, which indicate that there is an edge between $i$ and $f_i$ ($1\leq f_i\leq i-1$). The next line contains an integer $m$, representing the number of queries. The next $m$ lines describe all queries. Each line contains four integers $p_0,d_0,p_1,d_1$ ($1\leq p_0,p_1\leq n,0\leq d_0,d_1\leq n-1$), describing one query.

Output $m$ lines, answering the queries in order. Each line outputs one integer, which is the answer to that query.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078 Constraints: for $100\%$ of the data, $1\leq n\leq 10^5$ and $1\leq m\leq 10^5$. Translated by ChatGPT 5