P9250 [CTT Homework 2019] The Hard Road to Shu

“The road to Shu is hard, harder than climbing to the sky…” While reciting the newly learned Chinese text, A and B walked out of the north campus gate. It had been a long time since the 7 p.m. dismissal, and there was still some time before the crowd after the 10:45 p.m. evening study. The alley was sparsely populated. “The exam is tomorrow morning.” A said softly and stiffly. “Mm… memorizing a text like this really gives a sense of the carefree pride of poets.” B replied. “Come on. Have we learned any ‘literature’? Every day we sit in the computer lab, type code, and grind problems. When we get emotional, we can only live on two or three lines of poetry learned in Chinese class.” “Life is hard, don’t expose it… Tell me, did the people of the ancient Shu kingdom three thousand years ago really travel by ‘sky ladders and stone plank roads linked together’?” “They lived in the Sichuan Basin, the land of abundance, okay? Those who lived in the mountains were the Miao and other mountain tribes. How could they cross mountains and walk plank roads every day? Plank roads were built on a large scale only hundreds of years later when Qin developed Shu.” “Then the people up ahead, like on the Loess Plateau, do they have to shout to talk?” “Maybe they were ‘hearing each other’s chickens and dogs, yet never visiting each other until death’, so they didn’t need to communicate like that at all.” “Compared with that, I’d rather they truly had heroes like ‘the earth collapsing and mountains crushed, strong men died’.” “Who can be sure about things from thousands of years ago.” “You can’t say that… I’d rather believe information is conserved, and everything in history leaves traces.” “Then go do archaeology.” “But do you know chaos?” A, left speechless, stopped with B under that locust tree. Suddenly, he recited clearly and rhythmically: “Above are the lofty peaks where six dragons turn the sun back—below are the winding rivers where surging waves crash upstream. The yellow crane’s flight—still cannot pass; even the gibbons that would cross, sorrowfully cling and climb.” “Why is Qingni so winding, every hundred steps nine turns around the cliffs. Touching the stars and passing the constellations, one looks up and holds one’s breath; with a hand on the chest, one sits and sighs.” B, staring at the trunk in a daze, also echoed softly. Then, as usual, that girl appeared from behind the tree trunk. She was still in white, wearing a flower crown, smiling gently, silent. A still lowered his head slightly and played with the corner of his clothes; B also smiled as always. She stroked their heads, and A and B did not call 110 this time either. In an instant, a hazy feeling flashed by. Facing the peaks and valleys, the continuous ridges and deep gorges, A could not help recalling Li Daoyuan’s line from middle school: “Layered cliffs and overlapping peaks, blocking out the sky and covering the sun; unless it is noon at midnight, one cannot see the sun or the moon.” The very remark he had used to mock B—regretting too little reading when needed—instead seeped into his own heart. In the distance, stone chambers by the water were faintly visible, seemingly inhabited; silhouettes of houses appeared on the mountaintop. Suddenly B held A’s hand. Only then did A, intoxicated by gibbon cries and bird calls, realize that he was in a dream brought by LCR. “This seems to be exactly what we were discussing in ‘The Hard Road to Shu’ just now.” A thought so too, but he did not see any plank road. It seemed this was an even earlier “mountain tribe” than the Qin king. “Then let’s actually observe the question we just raised. How do people communicate without plank roads?” The most direct way would be to cling to vines and cross mountains—an inherent skill of mountain-dwelling ancestors. But skill cannot eliminate the danger of snakes, insects, and missteps in the mountains. Using this to pass information would be not worth the cost. B believed there was a more specialized method. The valley gradually brightened. Sharp-eyed A noticed something unusual on the cliff face covered by trees. The two climbed over; thanks to the dream, they made little effort. It turned out that along the mountains ran a bamboo tube split open and fixed with thin bamboo strips, about a foot wide. Spring water flowed through it—probably a water-diversion facility used by the mountain people. “That’s not right. People down the mountain can take water from the river in the valley. And if you want to transport water, you should use a complete pipe rather than a split one.” Then, a small bamboo tube tied with a string slid past them in the water channel. “This is…” “Yes! This little tube is a tool for exchanging small items—including information carriers—between the top and bottom of the mountain. The flowing water is to wash away sediment. Using a split bamboo tube instead of a sealed one is also to prevent it from getting stuck.” “But isn’t it easy for the small tube to slip out of a channel that’s only half a pipe?” “Look carefully. The small tube is made of two segments, so it can take in water when storing information. The spring water also guides its motion. And the string above can be pulled back—this means the communication is two-way. Even though the initiator is always at the higher place, they can just wait to solve the opposite direction.” “Probably so. But this is the world brought by LCR; we don’t know whether our ancestors really did this in the Qinba Mountains.” “If there is a stable clear spring, it should work.” “This kind of idea,” B said, “shows that the ancestors understood that technique can be better than science.” Then he suddenly fell silent. “Is it really so?” Then the two floated up—reminding them they were in a dream. A noticed that near this mountain, there were many such water-transport “channels”, forming a large tree-shaped network. “They not only invented this method, but also made a plan that fits scientific principles and is full of wisdom.” “Look. They connected all settlements with routes using the minimum number of segments. If you sort the heights of all settlements, they form an arithmetic progression. Between any two settlements, they can communicate with at most one intermediate settlement relaying. Their pipes save height differences the most.” No one knew who was speaking. … After thinking for a while, A said: “That is, although the positions of settlements are constrained by nature and cannot be moved, they made the wisest choice in how to connect pipes.” B replied: “Yes. What LCR meant, described in OI terms, is probably this: pipes can be seen as edges between settlements. 1. They connect the settlements with minimum total cost, i.e. form a tree; 2. Pipes at the same settlement are interconnected and managed; that is, as long as the height directions of pipes between two settlements are monotone—settlement heights strictly increase or strictly decrease—they can communicate directly. 3. Communication between any two settlements needs at most one forwarding; 4. After sorting, all settlement heights form an arithmetic progression; 5. The cost of a pipe is proportional to the height difference of its endpoints, and the sum of costs formed by these height differences happens to be the minimum among all possible arrangements of settlement heights;” “But settlement heights are not decided by people.” “So, this is the beauty of mathematics, a crystallization of nature’s coincidence and human wisdom together. Nothing is more romantic than this.” “Fine… but if a new settlement is added, everything is ruined.” “Luckily, this is a dream world. Maybe we can play the savior and change the settlement heights.” “Then how do we do that?” **“First is abstraction. We view the settlements as a tree with $n$ nodes. The nodes are labeled from $1$ to $n$. The weight of an edge is the absolute difference of the labels of its endpoints. The weight of the whole tree is the sum of all edge weights. In addition, the tree must satisfy a condition: for any two nodes, either the labels along the path between them (including endpoints) are monotone (increasing or decreasing), or there exists a third node such that it satisfies this condition with each of the two nodes.** **Then our task is: for a given tree shape, under these assumptions, find the minimum possible total weight of the whole tree by changing the node labeling method.** **Moreover, we also need to maintain this after adding a new leaf.”** … The 11 o’clock bell was about to ring. Students passed by that locust tree one after another. No one noticed that, two hours earlier, two students had been sleepwalking under the tree. Please complete B’s idea. --- #### Statement Given a labeled rooted tree $T=(V,E)$, a labeling $p:v\rightarrow p(v),v\in V,p(v)\in [1,|V|]\cap \mathbb{Z}$ is a bijection. For an edge $e = (u,v),e\in E$, define its edge weight as $w:e\rightarrow w(e) = \lvert p(u)-p(v) \rvert,e\in E,w(e)\in \mathbb{Z}$. Define the total weight of the tree as $W:T=(V,E)\rightarrow W(T)=\sum_{e\in E}w(e)$. Also define a graph $G(T)=(V,E')$, where $(u,v)\in E'$ if and only if along the path from $u$ to $v$ in $T$, the sequence of labels $p_1,p_2,\cdots , p_l$ is either monotonically increasing or monotonically decreasing. Then $p$ must make the diameter of $G(T)$ at most $2$, i.e. $\mathop{\max}_{i,j\in V}SP(i,j)\le 2$, where $SP(i,j)$ denotes the number of edges on the shortest path between $i$ and $j$ in $G(T)$. Now given $T$, compute $M(T)=\mathop{\min}_{p}W(T)$. There are also several operations: add a new leaf $v$ to $T$ ($V\gets V\cup \{v\}$, $E\gets E\cup \{(x,v)\}$, $x\in V_{old}$). After each operation, you also need to output $M(T)$. These operations are performed sequentially.

The first line contains a positive integer $n$ denoting the initial $\lvert V\rvert$. These nodes will be represented by integers from $1$ to $n$ in the following format; please do not confuse them with the labeling $p$ to be determined. In the next $n-1$ lines, the $i$-th line contains two positive integers $u_i,v_i$, representing the initial $E=\{(u_i,v_i):i=1,2,\dots ,n-1\}$. It is guaranteed that $u_i < v_i = i+1$. The next line contains a non-negative integer $q$ denoting the number of modifications. In the next $q$ lines, the $i$-th line contains a positive integer $f_i$, meaning that a node (denoted as $n+i$) and a new edge $(f_i,n+i)$ are added.

Output $q+1$ lines. Each line contains a non-negative integer, representing $M(T)$ for the initial tree and after each modification, in order.

### Sample Explanation $\mathbf{1}$ Each time, the tree is a chain (`1`, `1-2`, `3-1-2`). Let $p(i)$ be the number of nodes from $i$ to the end of the chain that was added later in the input. ### Constraints For all data, $1\le n\le 10^5$，$0\le q\le 10^5$，$1\le n+q\le 10^5$. The detailed limits and notes for each subtask are as follows (blank means the same as the overall constraints above): |Subtask ID|Score|$n$|$q$|Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$5$|$\le 10$|$\le 10$|-| |$2$|$10$|$\le 18$|$\le 18$|-| |$3$|$10$|$\le 100$|$=0$|-| |$4$|$10$|$\le 2000$|$=0$|-| |$5$|$10$| |$=0$|-| |$6$|$10$| | |I| |$7$|$10$| | |II| |$8$|$15$| | |III| |$9$|$20$| | |-| Property I: $\forall i,u_i,f_i\le 2$. Property II: $\forall i,u_i,f_i\le 20$. Property III: $\forall i,u_i$ are uniformly random in $1,2, \dots ,i-1$; $\forall i,f_i$ are uniformly random in $1,2, \dots ,n+i-1$. **Note: Subtask #10 of this problem is hack testdata worth $\mathbf{0}$ points. It is not included in the total score, but if you fail on it, you will not be accepted.** Translated by ChatGPT 5