将boss看成树根，那么上司与下属的关系就是图论中的有向边，本题本质是一个有向无环图，最终要求的是boss的收入也就是树根的收入，直接建图然后跑一遍dfs，每次用子结点更新父节点即可。

假如$u$为父节点,$v$是子节点,那么有val[u]+=val[v]/100*15

c++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
map<int,int>mp,s;
int f[N];
vector<int>g[N];
int idx=0;
ll val[N];
void dfs(int u)
{
    for(auto v:g[u])
    {
        dfs(v);
        val[u]+=(val[v]/100)*15;//更新父节点
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    memset(f,-1,sizeof f);//初始化为-1方便找根节点
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        //离散化
        if(!mp[a])mp[a]=++idx,s[idx]=a;
        if(!mp[b])mp[b]=++idx,s[idx]=b;
        g[mp[b]].push_back({mp[a]});
        f[mp[a]]=mp[b];
        val[mp[a]]=c;
    }
    int root=-1;
    for(auto i:mp)//找根节点
    {
        if(f[i.second]==-1)
        {
            root=i.second;
            break;
        }
    }
    dfs(root);
    cout<<s[root]<<" "<<val[root];
}

python

from collections import defaultdict

# 常量
N = int(1e5 + 10)  # 定义最大数组长度

# 映射和列表
mp = {}  # 用于存储节点值与其索引的映射
s = {}  # 用于存储索引对应的节点值
f = [-1] * N  # 用于存储每个节点的父节点，初始化为 -1
g = defaultdict(list)  # 图的邻接表表示法，存储子节点
val = [0] * N  # 存储每个节点的值
idx = 0  # 用于索引计数

# 深度优先搜索（DFS）函数
def dfs(u):
    # 遍历节点 u 的所有子节点 v
    for v in g[u]:
        dfs(v)  # 递归遍历子节点
        # 更新节点 u 的值，增加子节点贡献的 15%
        val[u] += (val[v] // 100) * 15

# 主函数
def main():
    global idx  # 声明 idx 为全局变量
    n = int(input())  # 输入节点数
    
    # 输入每个节点的关系及其初始值
    for i in range(1, n + 1):
        a, b, c = map(int, input().split())  # 输入 a, b 节点和 a 的初始值
        
        # 如果节点 a 不在映射中，添加到映射并分配索引
        if a not in mp:
            idx += 1
            mp[a] = idx
            s[idx] = a
        
        # 如果节点 b 不在映射中，添加到映射并分配索引
        if b not in mp:
            idx += 1
            mp[b] = idx
            s[idx] = b
        
        # 构建图的关系：b 指向 a
        g[mp[b]].append(mp[a])
        f[mp[a]] = mp[b]  # 设置 a 的父节点为 b
        val[mp[a]] = c  # 设置节点 a 的初始值为 c
    
    # 找到根节点（即父节点为 -1 的节点）
    root = -1
    for key, value in mp.items():
        if f[value] == -1:
            root = value  # 找到根节点并退出循环
            break
    
  
    dfs(root)
    

    print(s[root], val[root])

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    // 常量 N 表示数组的最大长度
    static final int N = 100010;
    
    // 映射和数组的初始化
    static Map<Integer, Integer> mp = new HashMap<>(); // 存储节点值与索引的映射
    static Map<Integer, Integer> s = new HashMap<>();  // 存储索引与节点值的映射
    static int[] f = new int[N];  // 存储每个节点的父节点，初始值为 -1
    static List<Integer>[] g = new ArrayList[N];  // 图的邻接表，用于存储每个节点的子节点
    static long[] val = new long[N];  // 存储每个节点的值
    static int idx = 0;  // 索引计数

    // 深度优先搜索（DFS）函数
    static void dfs(int u) {
        // 遍历节点 u 的所有子节点 v
        for (int v : g[u]) {
            dfs(v);  // 递归访问子节点
            // 累计当前节点 u 的值，增加子节点贡献的 15%
            val[u] += (val[v] / 100) * 15;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 初始化每个节点的邻接表
        for (int i = 0; i < N; i++) {
            g[i] = new ArrayList<>();
        }
        
        int n = sc.nextInt();  // 输入节点的数量
        Arrays.fill(f, -1);  // 初始化父节点数组 f，每个元素设为 -1

        // 输入节点关系及初始值
        for (int i = 1; i <= n; i++) {
            int a = sc.nextInt();  // 节点 a
            int b = sc.nextInt();  // 节点 b（a 的父节点）
            int c = sc.nextInt();  // 节点 a 的初始值

            // 如果节点 a 不在映射中，则添加
            if (!mp.containsKey(a)) {
                mp.put(a, ++idx);
                s.put(idx, a);
            }
            // 如果节点 b 不在映射中，则添加
            if (!mp.containsKey(b)) {
                mp.put(b, ++idx);
                s.put(idx, b);
            }

            // 在邻接表中将 a 添加到 b 的子节点列表中
            g[mp.get(b)].add(mp.get(a));
            // 设置 a 的父节点为 b
            f[mp.get(a)] = mp.get(b);
            // 设置 a 的初始值为 c
            val[mp.get(a)] = c;
        }

        int root = -1;  // 根节点初始化为 -1
        // 找到根节点（即父节点为 -1 的节点）
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            if (f[entry.getValue()] == -1) {
                root = entry.getValue();
                break;
            }
        }

        // 从根节点开始进行 DFS 遍历
        dfs(root);
        // 输出根节点的值及其累计的总值
        System.out.println(s.get(root) + " " + val[root]);
    }
}

题目内容

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

输入

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

输出

0 120