#P11766. 「KFCOI Round #1」遥不可及
「KFCOI Round #1」遥不可及
题目背景
你未曾料到,烟火散尽,余烬渐冷,那一转身的轻易告别,却成了永远的诀别。
但是,你决意追寻她的身影,哪怕在这永无止境的重逢梦中。
题目描述
个地点构成了复杂的关系网。
但是现在这些地点复杂的路线关系被简化成为了一棵树。
你从每个点均出发一次,当你从点 出发时,你会找到这个点能到达的所有最远点 ,并对每个 ,将 到 简单路径上的点权值加 。
询问最终所有地点的权值总和。
输入格式
本题输入均为正整数。
第一行一个数 ,表示有 个地点。
接下来 行,每行三个整数 表示一条边。
输出格式
一行一个数,表示所有地点最后的权值总和。
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
提示
样例一解释:
从 出发,最远距离为 ,故到达 和 ,各点权为 ;
从 出发,最远距离为 ,故到达 和 ,各点权为 ;
从 出发,最远距离为 ,故到达 和 ,各点权为 ;
从 出发,最远距离为 ,故到达 和 ,各点权为 ;
从 出发,最远距离为 ,故到达 和 ,各点权为 ;
从 出发,最远距离为 ,故到达 和 ,各点权为 。
所以最终各点权和为 。
(黄色为 出发的路径;红色为 ;蓝色为 ;绿色为 ;青色为 ;紫色为 。)
本题采用捆绑测试。
- Subtask 1(20 points,1 s):。
- Subtask 2(40 points,1 s):。
- Subtask 3(10 points,1 s):树的形态为链。
- Subtask 4(10 points,2 s):树的形态为菊花。
- Subtask 5(20 points,2 s):无特殊限制。
对于所有测试数据,,,,。
本题输入数据较大,请使用较快的读入方式和实现方式。请注意本题的栈空间。