[集训队互测 2018] 蜀道难

「蜀道之难，难于上青天……」 一边背着新学的语文课文，A 与 B 走出北校门口。现在距离七点的放学时间已过很久，与十点四十五分晚自习后的人潮却还有些距离，巷里的行人稀稀落落的。 「明天早上就考试了呀。」A 小声而僵硬地说道。 「嗯……背这样的课文，还真有种文人墨客的潇洒豪气。」B 回应着。 「嗨，得了，我们学了什么『文』么？天天坐机房敲代码刷题，触景生情时也就靠语文课学的两三句诗过活了。」 「人艰不拆……你说，三千年前的古蜀国人真要凭『天梯石栈相勾连』往来吗？」 「人家住在四川盆地、天府之土好吗。住山里的，那是苗蛮，部落山野之人，怎么会天天翻山越岭走栈道呢？栈道那是几百年后，秦国经略蜀地才大规模修筑的。」 「那这前边的人，就跟黄土高原一样，说话靠吼么。」 「兴许他们是鸡犬之声相闻，老死不相往来，根本不用如此交流吧。」 「比起如此，我到更希望他们真有『地崩山摧壮士死』的英雄。」 「几千年前的事，谁又说得准呐。」 「不能这么说……我宁愿相信信息是守恒的，历史的一切都会留下痕迹。」 「那您考古嘞。」 「可你知道混沌吧。」 一时语塞的 A 带着两人在那棵槐树下停止了脚步。 突然他字正腔圆，有板有眼地念着： 「上有六龙回日之高标——下有冲波逆折之回川。黄鹤之飞——尚不得过，猿猱欲度，愁攀援。」 「青泥何盘盘，百步九折萦岩峦。扪参历井仰胁息，以手抚膺坐长叹。」正望着树干出神的 B 也轻声应和。 然后，一如往日，那名女孩也从树干背后现身了，仍是一袭白衣，头戴花冠，浅笑嫣然，缄口不言。A 仍是微微低头把玩衣角，B 也照常微笑。 她抚摸着他们的头，A 和 B 也没有再拨打 110 报警。倏忽间闪过恍惚。 面对眼前的高峰幽谷、连山绝壑，A 不禁想起了初中所学郦道元的「重岩叠嶂，隐天蔽日，自非亭午夜分，不见曦月。」刚刚讽刺 B 的，书到用时方恨少的发言，反而沁入自己的心脾了。远处的水滨石室隐约可见，似有人烟；山顶处则现出房屋的剪影。 突然手被 B 握住。陶醉在猿啼鸟鸣中的 A 这才惊觉，自己身处 LCR 带来的梦境。 「这好像是我们刚刚所讨论《蜀道难》的内容啊。」 A 也想到了，但他并未看到栈道的影子，看来这是比秦王更早的「苗蛮」了。 「那我们实际观察一下刚刚的问题吧。没有栈道的人如何交流。」 最直接的方法，当属攀藤附葛，翻山越岭而至，这也是靠山吃山的先民们固有的技能——但技艺的熟练并不能抵消山中蛇虫和失足的危险。如此传递信息，未免得不偿失。B 相信存在更专业的手段。 山谷渐渐明亮起来，眼尖的 A 注意到树木遮掩的山壁有些不寻常。二人攀援而至，多亏是梦境，他们并未费力。原来，山间绵延着一根被劈开的，用细小竹片固定的，宽约尺余的竹筒。泉水从中流过，大概是山民们引水的设施。 「不对啊。山下的人有峪中河水可取。何况要输送水流，应该用完整而不是劈开的管道才对。」 接着，一支系绳的小竹筒从他们面前流着泉水的槽中滑过。 「这是……」 「是了！这小筒是山上山下交流少量物品——包括信息载体——的工具。流水是为了清除淤尘。劈开而非封闭的竹筒也是为了防止卡住。」 「可是，小筒不是很容易从仅仅一半的槽中滑落吗？」 「仔细观察，小筒是两节的结构，这样就能在存贮信息的时候接受水。泉水同样起了引流的作用。并且上面的绳子也能回收——这意味着交流是双向的，尽管发起者总在高处，但只需等待便可解决相反方向的问题。」 「大概如此，不过这是 LCR 带来的世界，不知我们的先辈是否真的在秦巴山区中如此做过。」 「若有一泓稳定的清泉，这应该可行。」 「这样的创意，」B 说，「表明先民们懂得技术胜过科学。」 接着他突然沉默了。「真的是这样吗？」 接着二人飘飞了起来——提醒着他们身处梦境的现实。 A 注意到，在这座山附近，这样流水传物的「信道」有许多，它们构成了一张树状的大网。 「他们不仅发明了这样的方法，还做了符合科学原理的，充满智慧的规划。」 「瞧瞧吧。他们用最少段数的路线连接了所有的聚落，他们的所有聚落的高度排序后恰好等差，他们的任意两个聚落之间只需经不超过一个聚落的转达即可互相通信，他们的管道高差最为节省。」 不知是谁在说呢。 …… A 思考了一会，说道： 「也就是说，尽管聚落的位置受自然条件限制是无法转移的，但他们在管道连接方案上做出了最明智的选择。」 B 答道： 「是啊。刚刚 LCR 的意思，以我们学的 OI 来描述大概是这样的：管道可以看作两个聚落之间的边。 1. 它们以最小代价联通聚落，即构成一棵树； 2. 同一个聚落处的管道是互联的且有人管理，也即两个聚落只要满足其间的管道的高度方向是单调的——聚落高度一直递增或一直递减——就可以直接通信。 3. 任意两个聚落通信至多需要转发一次； 4. 所有聚落的高度排序后恰是等差数列； 5. 管道的代价正比与两端聚落的高差，而高差形成的代价和恰巧是所有聚落高度排列方式中最小的；」 「但聚落的高度并不是人决定的。」 「所以，这一点是数学的美，是大自然的巧合和人的智慧共同的结晶。没有什么比这更浪漫了。」 「很好……但如果新加入一个聚落的话，事情就被破坏了。」 「幸运的是，这是梦境世界。我们也许可以做做救世主，改变一下聚落的高度。」 「那该怎么做呢？」 **「首先是抽象。我们把聚落看成一棵 $n$ 个点的树，树的点被标号为 $1$ 到 $n$，一条边的边权为两端点标号的差的绝对值。整棵树的权值为所有边权和。另外树必须满足一个条件：任意两点，要么它们之间（包括端点）的路径的标号是单调（递增或递减）的，要么存在第三点分别与这两点满足此条件。** **那么我们的任务是对于给定形态的树求出，在这些前提下通过改变点标号方法能得到的整棵树最小的权值。** **并且，还需要在加入新的叶子后维护这一点。」** …… 十一点钟声即将敲响，学生们陆续经过那棵槐树。没有人能注意到，两小时前两名同学在树下酣眠的梦游。 请你完成 B 的设想。 --- #### 题意 对于一棵有标号有根树 $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
2
1
1

0
1
2

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

4
6
7
8
10
11

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

### 样例解释 $\mathbf{1}$ 这棵树每次都是一条链（`1`、`1-2`、`3-1-2`），令 $p(i)$ 等于 $i$ 到链输入时间较晚的一端的点数即可。 ### 数据范围 对于所有数据，$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$|$\le 10$|-| |$2$|$10$|$\le 18$|$\le 18$|-| |$3$|$10$|$\le 100$|$=0$|-| |$4$|$10$|$\le 2000$|$=0$|-| |$5$|$10$| |$=0$|-| |$6$|$10$| | |一| |$7$|$10$| | |二| |$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$ 中均匀随机。 **注：本题 Subtask #10 为 $\mathbf{0}$ 分的 hack 数据，不计入总分，当如果错误则不予通过。**