J9 例题-1 积极分子看直播

题目描述

随着脑力奥运的开幕，在集训的积极分子们悄悄有乐子了，他们常常围聚在某个人的电脑旁看脑力奥运的直播。但是，积极分子乐于助人的性质决定了：他们都不怎么想移动别人的位置，于是在谁的电脑上看直播成了积极分子争吵的问题。当然，积极分子都是极其聪明的，他们马上把问题抽象为一个二叉树结构（如下图，其中圈内的数字表示积极分子移动一格所消耗的体力值，圈边上数字表示积极分子的编号）。 他们把这个问题转换成：在树上找一个点，使得所有人移动的体力消耗值最小。如图所示，若在1号积极分子处看直播，则各积极分子的移动消耗的体力值总和：$4+12+2*20+2*40=136$；若在 $3$ 号积极分子处看直播，则各积极分子的移动消耗的体力值总和：$4*2+13+20+40=81$。（注意，相邻节点之间的距离为 $1$），显然，在 $3$ 号处看直播大家会更高兴。

现在，积极分子们希望移动消耗的体力值总和尽可能少，这个问题交给你解决。

输入格式

输入第一行一个整数 $n$，表示树的结点数 。 接下来的 $n$ 行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数表示移动艰难值；第二个数为左链接，为 $0$ 表示无链接；第三个数为右链接，为 $0$ 表示无链接。

共 $n+1$ 行： 第一行一个整数 $n$，表示总共有 $n$ 个积极分子。 接下来的 $n$ 行，每行描述了一个积极分子的状况，包含三个整数：移动一格消耗的体力值，左邻居（值为坐在此积极分子左边的同学编号，如果 $0$ ，则表示左边没有人），右邻居，含义同上。

输出格式

一个整数，表示全部积极分子最小的移动消耗的体力值总。

样例输入

5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

样例输出

81

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \leq n \leq 100$，移动一格消耗的体力值 $\le 100$。