#P11766. 「KFCOI Round #1」遥不可及

    ID: 12777 远端评测题 1000~2000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>洛谷原创O2优化树形 DP洛谷比赛

「KFCOI Round #1」遥不可及

题目背景

你未曾料到,烟火散尽,余烬渐冷,那一转身的轻易告别,却成了永远的诀别。

但是,你决意追寻她的身影,哪怕在这永无止境的重逢梦中。

题目描述

nn 个地点构成了复杂的关系网。

但是现在这些地点复杂的路线关系被简化成为了一棵树

你从每个点均出发一次,当你从点 uu 出发时,你会找到这个点能到达的所有最远点 v1,v2,vkv_1,v_2,\cdots v_k,并对每个 viv_i,将 uuviv_i 简单路径上的点权值加 11

询问最终所有地点的权值总和。

输入格式

本题输入均为正整数。

第一行一个数 nn,表示有 nn 个地点。

接下来 n1n−1 行,每行三个整数 ai,bi,wia_i,b_i,w_i 表示一条边。

输出格式

一行一个数,表示所有地点最后的权值总和。

6
1 2 1
2 3 1
2 4 1
4 5 1
4 6 1
44
10
6 10 3
9 5 4
6 7 10
6 5 9
10 4 8
5 1 9
8 10 10
2 7 1
3 1 3
52

提示

样例一解释:

11 出发,最远距离为 33,故到达 5566,各点权为 [2,2,0,2,1,1][2,2,0,2,1,1]

22 出发,最远距离为 22,故到达 5566,各点权为 [2,4,0,4,2,2][2,4,0,4,2,2]

33 出发,最远距离为 33,故到达 5566,各点权为 [2,6,2,6,3,3][2,6,2,6,3,3]

44 出发,最远距离为 22,故到达 1133,各点权为 [3,8,3,8,3,3][3,8,3,8,3,3]

55 出发,最远距离为 33,故到达 1133,各点权为 [4,10,4,10,5,3][4,10,4,10,5,3]

66 出发,最远距离为 33,故到达 1133,各点权为 [5,12,5,12,5,5][5,12,5,12,5,5]

所以最终各点权和为 4444

(黄色为 11 出发的路径;红色为 22;蓝色为 33;绿色为 44;青色为 55;紫色为 66。)


本题采用捆绑测试

  • Subtask 1(20 points,1 s):1n50001\le n \le 5000
  • Subtask 2(40 points,1 s):1n5×1051\le n \le 5\times 10^5
  • Subtask 3(10 points,1 s):树的形态为链。
  • Subtask 4(10 points,2 s):树的形态为菊花。
  • Subtask 5(20 points,2 s):无特殊限制。

对于所有测试数据,1n1061\le n\le 10^61wi1091\le w_i \le 10^91ain1\le a_i \le n1bin1 \le b_i\le n

本题输入数据较大,请使用较快的读入方式和实现方式。请注意本题的栈空间。