题目描述

A company of $n$ employees is due for a restructuring. In the resulting hierarchy,represented as a rooted tree, every node will be the boss of its children.

Each employee has a list of bosses they will accept. In addition, all employees mustbe assigned a salary. The salary must be a positive integer, and the salary of eachboss must be larger than the sum of salaries of their immediate subordinates.

Your task is to structure the company so that all above conditions hold, and the sumof all the salaries is as small as possible.

输入格式

The first input line contains an integer $n$ : the number of employees. The employees are numbered $1,2,...,n$

.After this, the input contains $n$ lines that describe the preferences of the employees.The $i$th such line contains an integer $k_i$ , followed by a list of $k_i$ integers. The list consists of all employees that the $i$th employee accepts as their boss.

输出格式

You should output the lowest total salary among all valid restructurings. You can assume that at least one solution exists.

题目大意

[BalticOI 2016 Day1]上司们

题目描述

某公司有 $n$ 个职员，其职员之间的阶级关系可以用一棵有根树表示，每个结点都是其所有儿子的上司。
每个职员应当分配一个工资。工资是一个正整数，且每个上司的工资必须大于它所有直系下属的工资之和。
你的任务是找到一种工资分配方案，使得以上所有条件满足且工资之和尽量小。

输入格式

第一行包含一个整数 $n$，表示职员的个数，职员依次编号为 $1,2,\dots,n$。
接下来 $n$ 行，第 $i$ 行包含一个整数 $k_i$，以及一个包含 $k_i$ 个数的数列。这个数列表示第 $i$ 个员工的愿意接受的上司。

输出格式

输出所有方案中最小的工资之和，数据保证有解。

由 @I_love_him52 提供翻译

4
1 4
3 1 3 4
2 1 2
1 3

8

提示

Subtask 1 (22 points)

• $2\leq n \leq 10$

• $\sum^n_{i=1}k_i\leq 20$

Subtask 2 (45 points)

• $2\leq n \leq 100$

• $\sum^n_{i=1}k_i\leq 200$

Subtask 3 (33 points)

• $2\leq n \leq 5000$

• $\sum^n_{i=1}k_i\leq 10000$