from collections import defaultdict

edges = defaultdict(list)

sorce1 = defaultdict(int)  #严重问题

sorce2 = defaultdict(int)  #一般问题

res = 0

def dfs(u):
    global res
    for v in edges[u]:
        dfs(v)
        sorce1[u]+=sorce1[v]
        sorce2[u]+=sorce2[v]
        if u=='*' and (sorce1[v]*5+sorce2[v]*2>th):
            res+=1

th,n = map(int,input().split())
for i in range(n):
    a,b,c,d = map(str,input().split())
    d = int(d)
    if c == '0':
        sorce1[a]+=d
    else:
        sorce2[a]+=d
    if a not in edges[b]:
        edges[b].append(a)
dfs('*')
print(res)

题面描述:

在这道题目中，给定了一组以树形结构表示的云服务，每个节点记录着不同级别的问题及其数量。通过计算每个云服务的DI值（遗留问题缺陷密度），公式为 ( \text{DI值} = 5 \times \text{严重问题数} + 2 \times \text{一般问题数} )，判断其是否大于阈值，从而评估该云服务是否为风险服务。输入包括一个阈值和若干节点的信息，要求输出被评定为风险云服务的数量。

思路

给定一个森林（多棵树），要求统计所有节点的计算值的和超过阈值的树的数量。

我们从树的根节点出发，遍历树的每一个子节点，在回溯时将其严重问题和一般问题的数量记录到父节点上。这样在遍历完一棵树后，根节点就包含了整棵树严重问题和一般问题的数量。按照公式计算是否超过阈值即可。

判断某个节点为根节点，可以在读入数据时记录每个点的入度。如果一个点没有入度，那么其是根节点。

另一个方案是，将所有根节点都挂载“*”节点下作为子节点，后续对第一层的每个节点作为根遍历即可。

题解扩展

在这道题中，我们需要处理一个森林（由多棵树组成），并统计所有节点的计算值超过给定阈值的树的数量。计算值是通过对每棵树的根节点及其所有子节点的严重问题和一般问题数量进行累加计算得出的。

具体步骤如下：

1. 树的表示：我们使用邻接表表示树的结构。每个节点的子节点存储在一个映射中。
2. 节点属性：每个节点有两个属性：严重问题数和一般问题数。我们使用两个映射分别存储这些信息。
3. 识别根节点：通过记录每个节点的入度，可以识别出根节点。入度为0的节点即为根节点。
4. 深度优先搜索（DFS）：从根节点开始遍历树，递归计算每个节点的严重问题和一般问题数量，并在回溯过程中累加到父节点上。
5. 计算和判断：在遍历过程中，如果根节点的计算值超过阈值，则统计该树为风险树。

代码

C++

#include<bits/stdc++.h>

using namespace std;

// 使用映射来存储每个节点的子节点
map<string, vector<string>> edg;
// 用于存储每个节点的严重问题数
map<string, int> v1;
// 用于存储每个节点的一般问题数
map<string, int> v2;
// 统计超过阈值的树的数量
int res = 0;
// n为节点数量，m为阈值
int n, m;

// 深度优先搜索函数
void dfs(string u) {
    // 遍历当前节点u的所有子节点
    for (string v : edg[u]) {
        dfs(v); // 递归遍历子节点
        v1[u] += v1[v]; // 累加子节点的严重问题数到父节点u
        v2[u] += v2[v]; // 累加子节点的一般问题数到父节点u
        // 如果u为根节点且其计算值超过阈值，则统计该树
        if (u == "*" && v1[v] * 5 + v2[v] * 2 > m) {
            res++;
        }
    }
}

int main() {
    cin >> m >> n; // 输入阈值和节点数量
    for (int i = 0; i < n; i++) {
        string a, b, c; // a为服务节点，b为父节点，c为问题级别
        int d; // d为问题数量
        cin >> a >> b >> c >> d; // 输入节点信息
        // 根据问题级别更新相应的数量
        if (c == "0") {
            v1[a] += d; // 严重问题
        } else {
            v2[a] += d; // 一般问题
        }
        // 构建树的结构
        // 确保每个父节点只记录子节点一次
        if (find(edg[b].begin(), edg[b].end(), a) == edg[b].end()) {
            edg[b].push_back(a); // 将节点a添加为b的子节点
        }
    }

    // 以“*”节点为根开始深度优先搜索
    dfs("*");
    cout << res << endl; // 输出风险树的数量

    return 0;
}

python

from collections import defaultdict

# 使用defaultdict来存储每个节点的子节点
edg = defaultdict(list)
# 用于存储每个节点的严重问题数
v1 = defaultdict(int)
# 用于存储每个节点的一般问题数
v2 = defaultdict(int)
# 统计超过阈值的树的数量
res = 0

# 深度优先搜索函数
def dfs(u):
    global res
    # 遍历当前节点u的所有子节点
    for v in edg[u]:
        dfs(v)  # 递归遍历子节点
        v1[u] += v1[v]  # 累加子节点的严重问题数到父节点u
        v2[u] += v2[v]  # 累加子节点的一般问题数到父节点u
        # 如果u为根节点且其计算值超过阈值，则统计该树
        if u == "*" and (v1[v] * 5 + v2[v] * 2) > m:
            res += 1

# 主程序
if __name__ == "__main__":
    m, n = map(int, input().split())  # 输入阈值和节点数量
    for _ in range(n):
        a, b, c, d = input().split()  # 输入节点信息
        d = int(d)  # 将问题数量转换为整数
        # 根据问题级别更新相应的数量
        if c == "0":
            v1[a] += d  # 严重问题
        else:
            v2[a] += d  # 一般问题
        # 构建树的结构
        # 确保每个父节点只记录子节点一次
        if a not in edg[b]:
            edg[b].append(a)  # 将节点a添加为b的子节点

    # 以“*”节点为根开始深度优先搜索
    dfs("*")
    print(res)  # 输出风险树的数量

java

import java.util.*;

public class RiskyTrees {

    // 使用Map来存储每个节点的子节点
    private static Map<String, List<String>> edg = new HashMap<>();
    // 用于存储每个节点的严重问题数
    private static Map<String, Integer> v1 = new HashMap<>();
    // 用于存储每个节点的一般问题数
    private static Map<String, Integer> v2 = new HashMap<>();
    // 统计超过阈值的树的数量
    private static int res = 0;
    // 阈值
    private static int m;

    // 深度优先搜索函数
    private static void dfs(String u) {
        // 遍历当前节点u的所有子节点
        for (String v : edg.getOrDefault(u, new ArrayList<>())) {
            dfs(v);  // 递归遍历子节点
            v1.put(u, v1.getOrDefault(u, 0) + v1.getOrDefault(v, 0)); // 累加子节点的严重问题数
            v2.put(u, v2.getOrDefault(u, 0) + v2.getOrDefault(v, 0)); // 累加子节点的一般问题数
            // 如果u为根节点且其计算值超过阈值，则统计该树
            if (u.equals("*") && (v1.getOrDefault(v, 0) * 5 + v2.getOrDefault(v, 0) * 2) > m) {
                res++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();  // 输入阈值
        int n = scanner.nextInt();  // 输入节点数量
        scanner.nextLine();  // 读取行结束符

        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            String[] parts = line.split(" ");
            String a = parts[0];  // 节点名
            String b = parts[1];  // 父节点
            int c = Integer.parseInt(parts[2]);  // 问题级别
            int d = Integer.parseInt(parts[3]);  // 问题数量
            
            // 根据问题级别更新相应的数量
            if (c == 0) {
                v1.put(a, v1.getOrDefault(a, 0) + d);  // 严重问题
            } else {
                v2.put(a, v2.getOrDefault(a, 0) + d);  // 一般问题
            }
            
            // 构建树的结构
            edg.putIfAbsent(b, new ArrayList<>());
            if (!edg.get(b).contains(a)) {
                edg.get(b).add(a);  // 将节点a添加为b的子节点
            }
        }

        // 以“*”节点为根开始深度优先搜索
        dfs("*");
        System.out.println(res);  // 输出风险树的数量
    }
}