题目描述

「蜀道之难，难于上青天……」

……

题意

对于一棵有标号有根树 $T=(V,E)$，标号 $p:v\rightarrow p(v),v\in V,p(v)\in [1,|V|]\cap \mathbb{Z}$ 是一个一一映射。令一条边 $e = (u,v),e\in E$ 的边权为：$w:e\rightarrow w(e) = \lvert p(u)-p(v) \rvert,e\in E,w(e)\in \mathbb{Z}$。令整棵树的权为：$W:T=(V,E)\rightarrow W(T)=\sum_{e\in E}w(e)$。

另外定义一个图 $G(T)=(V,E')$，其中 $(u,v)\in E'$ 当且仅当在 $T$ 中 $u$ 到 $v$ 路径上点的标号 $p_1,p_2,\cdots , p_l$，要么单调递增，要么单调递减。则 $p$ 必须使得 $G(T)$ 的直径不超过 $2$，即 $\mathop{\max}_{i,j\in V}SP(i,j)\le 2$，其中 $SP(i,j)$ 表示 $G(T)$ 中 $i,j$ 的最短路经过的边数。

现在给定 $T$，求 $M(T)=\mathop{\min}_{p}W(T)$。

并且有若干次操作：在 $T$ 中加入一个新的叶子 $v$（$V\gets V\cup \{v\},E\gets E\cup \{(x,v)\},x\in V_{old}$），每次操作后也要求 $M(T)$。这些操作是一脉相承的。

输入格式

第一行一个正整数 $n$ 表示初始的 $\lvert V\rvert$，这些点在接下来的格式中将以 $1$ 到 $n$ 的整数表示，请不要将其与待定的标号 $p$ 混淆；

接下来 $n-1$ 行中，第 $i$ 行两个正整数 $u_i,v_i$，表示初始的 $E=\{(u_i,v_i):i=1,2,\dots ,n-1\}$，保证 $u_i < v_i = i+1$；

接下来一行一个非负整数 $q$ 表示修改次数；

接下来 $q$ 行中，第 $i$ 行一个正整数 $f_i$，表示添加一个点（用 $n+i$ 表示）和一条新边 $(f_i,n+i)$。

输出格式

共 $q+1$ 行，每行一个非负整数，依次表示初始和每次修改之后的 $M(T)$。

样例 1

输入

1
2
1
1

输出

0
1
2

这棵树每次都是一条链（1、1-2、3-1-2），令 $p(i)$ 等于 $i$ 到链输入时间较晚的一端的点数即可。

样例 2

输入

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

输出

4
6
7
8
10
11

样例 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

输出

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

数据范围与提示

对于所有数据，$1\le n\le 10^5, 0\le q\le 10^5, 1\le n+q\le 10^5$。

每个子任务详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

子任务编号	分数	$n$	$q$	性质
1	5	$\le 10$		-
2	10	$\le 18$
3		$\le 100$	$=0$
4		$\le 2000$
5
6				一
7				二
8	15			三
9	20			-

性质一：$\forall i,u_i,f_i\le 2$

性质二：$\forall i,u_i,f_i\le 20$

性质三：$\forall i,u_i$ 在 $1,2, \dots ,i-1$ 中均匀随机；$\forall i,f_i$ 在 $1,2, \dots ,n+i-1$ 中均匀随机。