#P12467. [2025年福建省队集训]棽荠郁

    ID: 11630 传统题 3000ms 888MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS树形 DP差分转化卷积转化双指针合并有序序列FHQ Treap 分裂合并按排名分裂小并大合并集合

[2025年福建省队集训]棽荠郁

题目描述

Yuki 有一棵包含 nn 个结点的树,每条边有一个边权 wiw_i,边权可能为负数。

定义 dis⁡(u,v)\operatorname{dis}(u,v) 表示树上结点 uu 到结点 vv 的路径上的边权之和。

定义一个排列 p1,…,pnp_1,\dots,p_n 的价值为 $\sum\limits_{i=1}^{n}\operatorname{dis}(p_i,p_{i \bmod n+1})$,你需要求出所有 1∼n1\sim n 的排列的最小价值。

输入格式

本题有多组测试数据。

输入的第一行包含两个正整数 c,Tc,T,分别表示测试点编号和测试数据组数。样例满足 c=0c=0。

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行包含一个正整数 nn。
  • 接下来 n−1n-1 行,第 ii 行包含三个正整数 ui,vi,wiu_i,v_i,w_i,表示树上有一条连接 ui,viu_i,v_i 的权值为 wiw_i 的边。

输出格式

对于每组测试数据,输出一行,包含一个整数,表示所有 1∼n1\sim n 的排列的最小价值。

样例 1 输入

0 2
5
1 2 4
1 3 1
2 4 2
2 5 3
7
1 2 -7
2 3 1
1 4 -4
4 5 -4
4 6 5
6 7 -1

样例 1 输出

20
-50

样例 1 解释

  • 对于第一组测试数据,其中一个价值最小的 1∼n1\sim n 的排列为 {3,1,2,4,5}\{3,1,2,4,5\},它的价值为 $\operatorname{dis}(3,1)+\operatorname{dis}(1,2)+\operatorname{dis}(2,4)+\operatorname{dis}(4,5)+\operatorname{dis}(5,3)=1+4+2+5+8=20$。
  • 对于第二组测试数据,其中一个价值最小的 1∼n1\sim n 的排列为 {2,4,3,5,1,6,7}\{2,4,3,5,1,6,7\}。

样例 2

见 lush/lush2.in 与 lush/lush2.ans。

样例 3

见 lush/lush3.in 与 lush/lush3.ans。

样例 4

见 lush/lush4.in 与 lush/lush4.ans。

样例 5

见 lush/lush5.in 与 lush/lush5.ans。

样例 6

见 lush/lush6.in 与 lush/lush6.ans。

样例 7

见 lush/lush7.in 与 lush/lush7.ans。

数据范围

对于所有测试数据,保证:

  • 1≤T≤31 \le T \le 3;
  • 2≤n≤2×1052 \le n \le 2 \times 10^5;
  • 1≤ui,vi≤n1 \le u_i,v_i \le n,−103≤wi≤103-10^3 \le w_i \le 10^3。
测试点编号 n≤n \le 特殊限制
1∼21\sim 2 2×1052 \times 10^5 wi≥0w_i \ge 0
3∼43\sim 4 1010 无
5∼95\sim 9 300300
10∼1310 \sim 13 50005000
14∼1814 \sim 18 2×1052 \times 10^5 保证 ui=i,vi=i+1u_i=i,v_i=i+1
19∼2519 \sim 25 无