#P17726. [2026年福建省队集训]最小割

[2026年福建省队集训]最小割

题目描述

小 ε\varepsilon 最近学习了最小割。

对于一张带边权的无向连通图 G=(V,E)G=(V,E),给定点集 S⊆VS\subseteq V,我们称一个边集 C⊆EC\subseteq E 是 SS 的一个割,当且仅当删去 CC 中的所有边后,SS 中任意两个不同的点都不连通。这个割的权值为 CC 中所有边的边权和。特别的,当 CC 为空集时,其权值为 00。SS 的最小割即为权值最小的割。

现在给定一棵 nn 个点的树 TT,每条边有非负整数边权。初始时 S=∅S=\varnothing,接下来会依次向 SS 中加入 nn 个点,第 ii 次加入点 aia_i。保证 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 是一个 11 到 nn 的排列。

每次加入后,小 ε\varepsilon 都想知道当前集合 SS 的最小割的权值。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入 11 中,c=0c=0。

对于每组测试数据:

  • 第一行一个正整数 nn,表示树的节点个数。
  • 接下来 n−1n-1 行,每行三个非负整数 ui,vi,wiu_i,v_i,w_i,表示第 ii 条边连接 ui,viu_i,v_i 两个点,边权为 wiw_i。
  • 最后一行 nn 个正整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,其中第 ii 个正整数 aia_i 表示第 ii 次操作加入的点的编号。

输出格式

对于每组测试数据输出一行 nn 个非负整数,其中第 ii 个非负整数表示第 ii 次加入后,当前集合 SS 的最小割的权值。

样例

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

对于第一组数据:

  • 第 11 次加入后 S={1}S=\{1\},割 C={}C=\{\} 最优,其权值为 00;
  • 第 22 次加入后 S={1,3}S=\{1,3\},割 C={(2,3)}C=\{(2,3)\} 最优,其权值为 11;
  • 第 33 次加入后 S={1,3,4}S=\{1,3,4\},割 C={(2,3),(2,4)}C=\{(2,3),(2,4)\} 最优,其权值为 55;
  • 第 44 次加入后 S={1,2,3,4}S=\{1,2,3,4\},割 C={(1,2),(2,3),(2,4)}C=\{(1,2),(2,3),(2,4)\} 最优,其权值为 1010。

对于第二组数据:

  • 第 11 次加入后 S={2}S=\{2\},割 C={}C=\{\} 最优,其权值为 00;
  • 第 22 次加入后 S={2,4}S=\{2,4\},割 C={(2,3)}C=\{(2,3)\} 最优,其权值为 22;
  • 第 33 次加入后 S={1,2,4}S=\{1,2,4\},割 C={(1,2),(2,3)}C=\{(1,2),(2,3)\} 最优,其权值为 55;
  • 第 44 次加入后 S={1,2,4,5}S=\{1,2,4,5\},割 C={(1,2),(2,3),(4,5)}C=\{(1,2),(2,3),(4,5)\} 最优,其权值为 1111;
  • 第 55 次加入后 S={1,2,3,4,5}S=\{1,2,3,4,5\},割 C={(1,2),(2,3),(3,4),(4,5)}C=\{(1,2),(2,3),(3,4),(4,5)\} 最优,其权值为 1818。

数据范围

对于所有测试数据:

  • 1≤T≤51\le T\le 5;
  • 1≤n≤1061\le n\le 10^6;
  • 1≤ui,vi≤n1\le u_i,v_i\le n,0≤wi≤1090\le w_i\le 10^9;
  • 保证给出的图是一棵树;
  • a1,a2,⋯ ,ana_1,a_2,\cdots,a_n 是一个 11 到 nn 的排列。
测试点编号 n≤n\le 特殊性质
1∼21\sim 2 88 无
3∼53\sim 5 1818
66 50005000 A
77 B
88 C
99 D
10∼1110\sim 11 无
12∼1412\sim 14 2×1052\times 10^5 A
1515 B
16∼1716\sim 17 C
18∼1918\sim 19 D
20∼2220\sim 22 无
23∼2523\sim 25 10610^6
  • 特殊性质 A:树是一条链,对于任意 1≤i<n1\le i<n,存在一条连接 ii 与 i+1i+1 的边;
  • 特殊性质 B:树是一棵菊花,即所有边均与 11 号节点相连;
  • 特殊性质 C:wi=1w_i=1;
  • 特殊性质 D:0≤wi≤10\le w_i\le 1。