题目描述

一个XX产品行销总公司，只有一个 boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。

规定，每个月，下级分销需要将自己的总收入(自已的+下级上交的)每满100元上交15元给自己的上级

现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入。

比如:

• 收入100元，上交15元:

• 收入199元(99元不够100)，上交15元:。

收入200元，上交30元。

输入

分销关系和收入:[[分销id上级分销id收入]，[分销id上级分销id收入]，[分销id 上级分销id 收入]]

• 分销ID范围: 0..65535

• 收入范围: 0..65535，单位元

提示:

输入的数据只存在1个boss，不存在环路

输出

[boss的ID，总收入]

输入描述

第一行输入关系的总数量 N

第二行开始，输入关系信息，格式:

分销ID上级分销ID收入

比如:

5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

输出描述：

输出:

boss的ID总收入

0 120

说明

给定的输入数据都是合法的,不存在环路,重复的

题解

1. 根据给定的关系，构建一棵组织关系树
2. 找到树的根节点，从任意一个节点开始向上搜索，没有父节点的就是 boss 节点
3. 从树的boss点做 dfs 搜索，计算可以得到的总金额

参考 BOSS的收入 E100