一道树论

题目描述

小$W$现在有一个点集$S$和一棵树，树上有$n$个点和$n-1$条有边权的无向边。

但是小$W$很好奇，如果他想要断掉一些边，使得点集$S$内的点两两不连通，怎么做才能使要断掉的边的边权和最小呢？

他把这个问题丢给了你，想让你来回答，你只用告诉他要断的边的边权和是多少即可。

但他又觉得太简单了，所以他会一个个把$1$~$n$这些点以某个顺序插入$S$中（初始$S$为空），你要在每次插入后都回答他这个问题。

输入格式

第一行一个数，表示$n$。

接下来$n-1$行，第$i$行三个数$x_{i}$，$y_{i}$，$z_{i}$表示第$i$条边连接点$x_{i}$和$y_{i}$，边权为$z_{i}$。

再接下来$n$行，第$i$行一个数$a_{i}$，表示第$i$次要往$S$中插入点$a_{i}$。

输出格式

共$n$行，第$i$行表示在第$i$次插入之后的答案。

数据范围与提示

• 对于$20\%$的数据，$n \leq 18$；
• 对于$40\%$的数据，$n \leq 10^{3}$；
• 对于$70\%$的数据，$n \leq 10^{5}$；
• 对于$100\%$的数据，$1 \leq n \leq 5 \times 10^{5}$，$1 \leq z_{i} \leq 10^{9}$，保证$a$为$1$~$n$的一个排列。

样例

5
3 1 8
2 3 8
2 4 8
2 5 7
3
4
1
5
2

0
8
16
23
31

说明

• 第一次：$S=\{3\}$，不用断边；
• 第二次：$S=\{3,4\}$，可以断掉边集$\{3\}$或$\{2\}$；
• 第三次：$S=\{3,4,1\}$，可以断掉边集$\{1,3\}$或$\{1,2\}$；
• 第四次：$S=\{3,4,1,5\}$，可以断掉边集$\{1,3,4\}$或$\{1,2,4\}$；
• 第五次：$S=\{3,4,1,5,2\}$，可以断掉边集$\{1,2,3,4\}$。

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

0
2
3
4
11
20

见tree3.in

见tree3.ans