Problem Description

"The difficulty of the Shu Road is harder than ascending to the sky..."

Reciting the newly learned Chinese literature, A and B walked out of the north school gate. It had been a long time since the seven o'clock dismissal, and the crowd after the ten forty-five evening self-study was still a bit away. The pedestrians in the alley were sparse.

"There's an exam tomorrow morning," A said softly and stiffly.

"Yeah... Reciting such a passage really gives a sense of the free and bold spirit of the literati." B responded.

"Oh, come on, what 'literature' have we learned? We sit in the computer room all day coding and solving problems. When we're moved by the scenery, we rely on a couple of lines of poetry from Chinese class to get by."

"Life is tough... You know, did the ancient Shu people from three thousand years ago really rely on 'sky ladders and stone plank roads' to travel?"

"They lived in the Sichuan Basin, the land of abundance, okay. Those living in the mountains were the Miao and Man tribes, people of the tribal wilderness, how could they be traversing mountain paths and plank roads every day? Plank roads were built on a large scale only after the Qin State began to manage the Shu region several hundred years later."

"So, the people before that, like the Loess Plateau, communicated by shouting?"

"Perhaps they were like the saying, 'The sounds of chickens and dogs are heard, yet they never visit each other until they die,' and they didn't need such communication at all."

"I'd rather believe they really had heroes who 'died in the collapse of mountains and destruction of earth.'"

"Who can be sure about things thousands of years ago?"

"You can't say that... I'd rather believe that information is conserved, and everything in history leaves traces."

"Then you should be an archaeologist."

"But you know about chaos, right?"

A was momentarily speechless and stopped with the two under a pagoda tree.

Suddenly, he enunciated clearly and rhythmically:

"Above, the six dragons circle the high markers—below, the surging waves reverse and twist. Even the flying yellow cranes—cannot pass, and the apes, wanting to cross, worry about climbing."

"How winding the Qingni path is, with twists every hundred steps around the cliffs. Touching the stars and holding one's breath, one pats the chest and sighs long." B, gazing at the tree trunk, also softly chimed in.

Then, as usual, the girl also appeared from behind the tree trunk, still in white, with a floral crown, smiling faintly and remaining silent. A still slightly lowered his head, playing with the hem of his clothes, and B also smiled as usual.

She stroked their heads, and A and B didn't call the police again. Suddenly, a flash of dizziness passed.

Facing the towering peaks and deep valleys, A couldn't help but recall what he learned in junior high from Li Daoyuan: "Layers of cliffs and peaks, hiding the sky and covering the sun, unless it's noon or midnight, you can't see the sun or moon." The words he just used to mock B, that one regrets not having enough knowledge when it's needed, now seeped into his own heart. The stone chambers by the distant waters were faintly visible, as if inhabited; the silhouette of houses appeared at the mountaintop.

Suddenly, B took A's hand. A, who had been intoxicated by the cries of monkeys and birds, was startled to realize he was in a dream brought by LCR.

"This seems to be the content of what we just discussed about 'The Difficulty of Shu Road.'"

A also thought of that, but he didn't see any traces of plank roads, so this must be even earlier than the Qin King's time, the Miao and Man tribes.

"Let's observe the problem we just discussed. How did people without plank roads communicate?"

The most direct method would be to climb vines and cling to rocks, traversing mountains and valleys, which was a natural skill for early people who lived off the mountains—but skill mastery couldn't offset the dangers of snakes and insects and falling. Such information transmission was not worth the risk. B believed there were more professional methods.

The valley gradually brightened, and A noticed something unusual on the mountain wall hidden by trees. The two climbed up, thanks to the dream, they didn't exert much effort. It turned out that there was a split bamboo tube, about a foot wide, fixed with small bamboo strips, running through the mountains. Water flowed through it, probably a water diversion facility for the mountain dwellers.

"That's not right. People at the foot of the mountain have river water to take. Moreover, to transport water, one should use an intact rather than a split pipe."

Then, a small bamboo tube tied with a rope slid past them in the water channel.

"This is..."

"Yes! This small tube is a tool for exchanging small items—including information carriers—between the mountains and the valleys. The water is to clear away the dust. The split rather than closed bamboo tube also prevents jamming."

"But wouldn't the small tube easily fall out of the half-open channel?"

"Observe carefully, the small tube is a two-section structure, so it can store information while receiving water. The water also serves to guide it. And the rope can be recovered—this means the communication is bidirectional, although the initiator is always at a higher place, but just waiting can solve the problem in the opposite direction."

"Probably so, but this is a world brought by LCR, I wonder if our ancestors really did this in the Qinba Mountains."

"If there's a stable spring, it should be feasible."

"Such an idea," B said, "shows that the ancients understood technology over science."

Then he suddenly fell silent. "Is that really the case?"

Then the two floated up—reminding them of the reality of the dream.

A noticed that around this mountain, there were many such water-transport channels, forming a large tree-like network.

"They not only invented this method but also made a scientifically principled, wise plan."

"Look. They connected all the settlements with the least number of routes, their settlements' heights, when sorted, form an arithmetic progression, any two settlements can communicate with each other with at most one relay, and the height difference of the pipes is the most economical."

Who knows who was speaking.

...

A thought for a while and said:

"That is to say, although the positions of the settlements are limited by natural conditions and cannot be moved, they made the wisest choice in the pipeline connection scheme."

B replied:

"Yes. What LCR meant, in terms of what we learned in OI, is probably this: the pipes can be seen as edges between settlements.

1. They connect the settlements at the minimum cost, forming a tree;
2. The pipes at the same settlement are interconnected and managed by people, that is, two settlements can directly communicate as long as the height direction of the pipes between them is monotonic—the settlement heights keep increasing or decreasing;
3. Any two settlements can communicate with at most one relay;
4. The heights of all settlements, when sorted, form an arithmetic sequence;
5. The cost of the pipes is proportional to the height difference between the two ends of the settlements, and the sum of the height differences forms the smallest possible cost among all settlement height arrangements;"

"But the heights of the settlements are not determined by humans."

"So, this is the beauty of mathematics, a combination of nature's coincidence and human wisdom. There's nothing more romantic than this."

"Good... But if a new settlement is added, things are disrupted."

"Fortunately, this is a dream world. We might be able to play the savior and change the heights of the settlements."

"So, how should we do it?"

"First, abstract it. We consider the settlements as a tree with $n$ points, the points are numbered from $1$ to $n$, and the weight of an edge is the absolute difference of the numbers of the two endpoints. The weight of the entire tree is the sum of all edge weights. Additionally, the tree must satisfy a condition: for any two points, either the path between them (including the endpoints) is monotonic (increasing or decreasing), or there exists a third point that satisfies this condition with each of these two points.

Our task is, given the shape of the tree, to find the minimum weight of the tree that can be achieved by changing the point numbers under these conditions.

Furthermore, we need to maintain this after adding new leaves."

...

The eleven o'clock bell was about to ring, and students passed by the pagoda tree one after another. No one noticed that two hours earlier, two classmates had been sleeping under the tree.

Please complete B's vision.

Problem Description

For 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 one-to-one mapping. Let the weight of an edge $e = (u,v),e\in E$ be: $w:e\rightarrow w(e) = \lvert p(u)-p(v) \rvert,e\in E,w(e)\in \mathbb{Z}$. Let the weight of the entire tree be: $W:T=(V,E)\rightarrow W(T)=\sum_{e\in E}w(e)$.

Additionally, define a graph $G(T)=(V,E')$, where $(u,v)\in E'$ if and only if in $T$, the labels $p_1,p_2,\cdots , p_l$ on the path from $u$ to $v$ are either monotonically increasing or decreasing. Then $p$ must ensure that the diameter of $G(T)$ is no more than $2$, i.e., $\mathop{\max}_{i,j\in V}SP(i,j)\le 2$, where $SP(i,j)$ represents the shortest path between $i$ and $j$ in $G(T)$.

Given $T$, find $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}$), and after each operation, also require $M(T)$. These operations are cumulative.

Input Format

The first line contains a positive integer $n$ representing the initial size of $V$, these points will be represented by integers from $1$ to $n$ in the following format, please do not confuse them with the pending labels $p$;
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\}$, ensuring $u_i < v_i = i+1$;
The next line contains a non-negative integer $q$ representing the number of modifications;
The next $q$ lines, the $i$-th line contains a positive integer $f_i$, representing the addition of a point (represented by $n+i$) and a new edge $(f_i,n+i)$.

Output Format

A total of $q+1$ lines, each containing a non-negative integer, sequentially representing the initial and after each modification $M(T)$.

Sample Input and Output

Input Sample #1

1
2
1
1

Output Sample #1

0
1
2

Input Sample #2

5
1 2
2 3
3 4
4 5
5
4
6
1
1
7

Output Sample #2

4
6
7
8
10
11

Input Sample #3

14
1 2
1 3
2 4
1 5
2 6
1 7
1 8
2 9
2 10
2 11
2 12
2 13
1 14
12
1
1
2
2
2
2
2
2
2
2
1
2

Output Sample #3

35
41
48
53
58
64
70
77
84
92
100
108
117

Notes/Hints

Sample Explanation #1

Each time the tree is a chain (1, 1-2, 3-1-2), let $p(i)$ be equal to the number of points from $i$ to the end of the chain that entered later.

Data Range

For all data, $1\le n\le 10^5$, $0\le q\le 10^5$, $1\le n+q\le 10^5$.

Detailed data constraints and conventions for each subtask are as follows (blank means the same as the above all data conventions):

Property 1: $\forall i,u_i,f_i\le 2$.

Property 2: $\forall i,u_i,f_i\le 20$.

Property 3: $\forall i,u_i$ is uniformly randomly chosen from $1,2, \dots ,i-1$; $\forall i,f_i$ is uniformly randomly chosen from $1,2, \dots ,n+i-1$.

Note: Subtask #10 is a 0-point hack data, not counted in the total score, but if incorrect, it will not pass.

见题面 Input 部分

见题面 Output 部分