#MX14. 树联网

树联网

题目描述

小蔡是一名树联网维护员。

具体地说,树联网的结构可以看作一颗树,用户就是树上的节点,边则是通信管道,每个通信管道都有一个脆弱值。

有一天,闲来无事的树联网用户们在所有通信管道中展开了一场大战,这使通信管道受到了损伤,每条通信管道受到的损伤值相当于通信管道两边用户数量之差乘以通信管道的脆弱值。

小蔡想知道,在这场大战过后,所有通信管道的损伤值之和是多少。

输入格式

第一行是一个整数nn,表示树联网上一共有nn个用户。

接下来nn行,每行包含三个整数aia_i,bib_i和cic_i,表示aia_i和bib_i节点之间有一条脆弱值为cic_i的通信管道。

保证数据一定会组成一棵树。

输出格式

输出一个整数,表示所有通信管道的损伤值之和。

样例

【样例 1 输入】

5
2 1 3
3 1 3
5 3 3
4 3 10

【样例 1 输出】

51

【样例 2 输入】

7
4 3 4
2 1 5
6 1 5
7 4 3
5 3 2
3 1 5

【样例 2 输出】

92

【样例 3 输入】

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

【样例 3 输出】

176

对于100%100\%的数据: 1≤ci≤106 1 \leq c_i \leq 10^6

测试点编号 nn
1∼51∼5 ≤104\leq 10^4
6∼106∼10 ≤106\leq 10^6

C选家具(furniture)

题目描述

小 D 最近搬家了,需要购置 aa 台家电、bb 件家具和 cc 个装饰。他来到了商场,商场正好在举行优惠大酬宾,每家店铺都推出了一系列活动。

一共有 n=a+b+cn=a+b+c 家店铺,活动期间在第 ii 家店铺购买家电只需要 aia_i 元一台,购买家具只需要 bib_i 元一件,购买装饰只需要 cic_i 元一个,但每一家店铺限定每位顾客最多只能购买一种类型的物品一个。

小 D 希望在满足采购需求的情况下总花费最少,你能帮帮他求出最小花费吗?

输入格式

一共一行四个整数 n,a,b,cn,a,b,c ,分别表示店铺的数量和小 D 需求的每一种类型物品的数量。

接下来一共 nn 行,每行三个非负整数 ai,bi,cia_i,b_i,c_i,含义如题。

输出格式

输出共一行一个整数,表示小 D 的最小花费。

样例一

输入格式

5 1 2 2
6 4 3
8 4 7
2 7 3
8 10 3
1 7 2

输出格式

15

样例解释

在第一,二家店各买一台家具,在第三、四家店各买一个装饰,在第五家店买一件家电。

一个花费 4+4+3+3+1=154+4+3+3+1=15 元。

数据范围

对于所有数据 n,a,b,c≤5000,ai,bi,ci≤109n,a,b,c\le 5000,a_i,b_i,c_i\le 10^9 ,保证 n=a+b+cn=a+b+c 。

测试点 数据范围
1∼41\sim 4 n≤15n\le 15
5∼105\sim 10 n≤100n\le 100
11∼1411\sim 14 c=0c=0
15∼2015\sim 20 无限制