题目描述

一个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

备注

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

示例一

输入

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

输出

0 120

说明

无

Java

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取分销关系的数量
        int n = Integer.parseInt(sc.nextLine().trim());

        // 记录每个分销商的收入
        HashMap<Integer, Long> income = new HashMap<>();
        // 记录所有的分销商 ID
        HashSet<Integer> ids = new HashSet<>();
        // 记录子分销商到父分销商的映射关系
        HashMap<Integer, Integer> childToParent = new HashMap<>();
        // 记录父分销商到其所有子分销商的映射关系
        HashMap<Integer, LinkedList<Integer>> parentToChildren = new HashMap<>();

        // 读取输入数据并构建映射关系
        for (int i = 0; i < n; i++) {
            // 读取当前行
            String[] parts = sc.nextLine().split(" ");
            // 解析当前子分销商的 ID
            int childId = Integer.parseInt(parts[0]);