A6530. 「BalticOI 2016 Day1」上司们
编程题
提高+/省选-
知识点
题目描述
**题目译自 [BalticOI 2016](https://www.cs.helsinki.fi/group/boi2016/tasks.shtml) [Day1](https://www.cs.helsinki.fi/group/boi2016/day1_tasks.zip) T1「Bosses」**
某公司有 $n$ 个职员，其职员之间的阶级关系可以用一棵有根树表示，每个结点都是其所有儿子的上司。
每个职员应当分配一个工资。工资是一个正整数，且每个上司的工资必须大于它所有直系下属的工资之和。
你的任务是找到一种工资分配方案，使得以上所有条件满足且工资之和尽量小。
某公司有 $n$ 个职员，其职员之间的阶级关系可以用一棵有根树表示，每个结点都是其所有儿子的上司。
每个职员应当分配一个工资。工资是一个正整数，且每个上司的工资必须大于它所有直系下属的工资之和。
你的任务是找到一种工资分配方案，使得以上所有条件满足且工资之和尽量小。
输入格式
第一行包含一个整数 $n$，表示职员的个数，职员依次编号为 $1,2,\dots,n$。
接下来 $n$ 行，第 $i$ 行包含一个整数 $k_i$，以及一个包含 $k_i$ 个数的数列。这个数列表示第 $i$ 个员工愿意接受的上司。
接下来 $n$ 行，第 $i$ 行包含一个整数 $k_i$，以及一个包含 $k_i$ 个数的数列。这个数列表示第 $i$ 个员工愿意接受的上司。
输出格式
输出所有方案中最小的工资之和，数据保证有解。
输入输出样例
输入 #1
4 1 4 3 1 3 4 2 1 2 1 3
输出 #1
8
说明/提示
|子任务|分数|数据范围|
|:-:|:-:|:-:|
|1|22|$2 \leq n \leq 10,\Sigma^n_{i = 1}k_i \leq 20$|
|2|45|$2 \leq n \leq 100,\Sigma^n_{i = 1}k_i \leq 200$|
|3|33|$2 \leq n \leq 5000,\Sigma^n_{i = 1}k_i \leq 10000$|
|:-:|:-:|:-:|
|1|22|$2 \leq n \leq 10,\Sigma^n_{i = 1}k_i \leq 20$|
|2|45|$2 \leq n \leq 100,\Sigma^n_{i = 1}k_i \leq 200$|
|3|33|$2 \leq n \leq 5000,\Sigma^n_{i = 1}k_i \leq 10000$|