题目描述
小 ε 最近学习了最小割。
对于一张带边权的无向连通图 G=(V,E),给定点集 S⊆V,我们称一个边集 C⊆E 是 S 的一个割,当且仅当删去 C 中的所有边后,S 中任意两个不同的点都不连通。这个割的权值为 C 中所有边的边权和。特别的,当 C 为空集时,其权值为 0。S 的最小割即为权值最小的割。
现在给定一棵 n 个点的树 T,每条边有非负整数边权。初始时 S=∅,接下来会依次向 S 中加入 n 个点,第 i 次加入点 ai。保证 a1,a2,⋯,an 是一个 1 到 n 的排列。
每次加入后,小 ε 都想知道当前集合 S 的最小割的权值。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入 1 中,c=0。
对于每组测试数据:
- 第一行一个正整数 n,表示树的节点个数。
- 接下来 n−1 行,每行三个非负整数 ui,vi,wi,表示第 i 条边连接 ui,vi 两个点,边权为 wi。
- 最后一行 n 个正整数 a1,a2,⋯,an,其中第 i 个正整数 ai 表示第 i 次操作加入的点的编号。
输出格式
对于每组测试数据输出一行 n 个非负整数,其中第 i 个非负整数表示第 i 次加入后,当前集合 S 的最小割的权值。
样例
样例输入 1
0 2
4
1 2 5
2 3 1
2 4 4
1 3 4 2
5
1 2 3
2 3 2
3 4 7
4 5 6
2 4 1 5 3
样例输出 1
0 1 5 10
0 2 5 11 18
样例解释 1
对于第一组数据:
- 第 1 次加入后 S={1},割 C={} 最优,其权值为 0;
- 第 2 次加入后 S={1,3},割 C={(2,3)} 最优,其权值为 1;
- 第 3 次加入后 S={1,3,4},割 C={(2,3),(2,4)} 最优,其权值为 5;
- 第 4 次加入后 S={1,2,3,4},割 C={(1,2),(2,3),(2,4)} 最优,其权值为 10。
对于第二组数据:
- 第 1 次加入后 S={2},割 C={} 最优,其权值为 0;
- 第 2 次加入后 S={2,4},割 C={(2,3)} 最优,其权值为 2;
- 第 3 次加入后 S={1,2,4},割 C={(1,2),(2,3)} 最优,其权值为 5;
- 第 4 次加入后 S={1,2,4,5},割 C={(1,2),(2,3),(4,5)} 最优,其权值为 11;
- 第 5 次加入后 S={1,2,3,4,5},割 C={(1,2),(2,3),(3,4),(4,5)} 最优,其权值为 18。
数据范围
对于所有测试数据:
- 1≤T≤5;
- 1≤n≤106;
- 1≤ui,vi≤n,0≤wi≤109;
- 保证给出的图是一棵树;
- a1,a2,⋯,an 是一个 1 到 n 的排列。
| 测试点编号 |
n≤ |
特殊性质 |
| 1∼2 |
8 |
无 |
| 3∼5 |
18 |
| 6 |
5000 |
A |
| 7 |
B |
| 8 |
C |
| 9 |
D |
| 10∼11 |
无 |
| 12∼14 |
2×105 |
A |
| 15 |
B |
| 16∼17 |
C |
| 18∼19 |
D |
| 20∼22 |
无 |
| 23∼25 |
106 |
- 特殊性质 A:树是一条链,对于任意 1≤i<n,存在一条连接 i 与 i+1 的边;
- 特殊性质 B:树是一棵菊花,即所有边均与 1 号节点相连;
- 特殊性质 C:wi=1;
- 特殊性质 D:0≤wi≤1。