题面描述:

在这道题目中，给定了一组以树形结构表示的云服务，每个节点记录着不同级别的问题及其数量。通过计算每个云服务的DI值（遗留问题缺陷密度），公式为 $\text{DI值} = 5 * \text{严重问题数} + 2 * \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 Main {

    // 使用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);  // 输出风险树的数量
    }
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    let edg = new Map(); // 存储树结构（父节点 -> 子节点列表）
    let v1 = new Map();  // 存储每个节点的严重问题数
    let v2 = new Map();  // 存储每个节点的一般问题数
    let res = 0; // 统计超过阈值的树数量

    let [m, n] = (await readline()).split(" ").map(Number);


    // 读取所有节点信息
    for (let i = 0; i < n; i++) {
        let [a, b, c, d] = (await readline()).split(" ");
        c = parseInt(c); // 问题级别
        d = parseInt(d); // 问题数量

        // 根据问题级别更新相应的数量
        if (c === 0) {
            v1.set(a, (v1.get(a) || 0) + d); // 严重问题
        } else {
            v2.set(a, (v2.get(a) || 0) + d); // 一般问题
        }

        // 构建树结构
        if (!edg.has(b)) edg.set(b, []);
        if (!edg.get(b).includes(a)) { 
            edg.get(b).push(a); // 添加节点 a
        }
    }

    // 深度优先搜索计算问题数
    function dfs(u) {
        if (!edg.has(u)) return; // 若无子节点，直接返回

        for (let v of edg.get(u)) {
            dfs(v);
            v1.set(u, (v1.get(u) || 0) + (v1.get(v) || 0)); // 累加子节点的严重问题数
            v2.set(u, (v2.get(u) || 0) + (v2.get(v) || 0)); // 累加子节点的一般问题数

            // 判断是否超出阈值
            let totalRisk = ((v1.get(v) || 0) * 5) + ((v2.get(v) || 0) * 2);
            if (u === "*" && totalRisk > m) {
                res++;
            }
        }
    }

    // 以 `*` 作为根节点执行 DFS
    dfs("*");

    console.log(res); // 输出风险树的数量
    rl.close();
})();

题目描述

$\qquad$要是你认为小明只做网站，那就大错特错了。其实小明还做点云服务，最近，小明忙着维护云服务器，没空跟你开黑。为了上分，你打算出手。

$\qquad$小明将云服务看做一棵树，每个云服务在发布前尚未解决的问题称为云服务的遗留问题（云服务的遗留问题包含以该云服务为根节点的树上所有节点的问题），DI值（遗留问题缺陷密度）可以作为评估云服务发布的指标，当云服务DI值小于等于阈值时才准许云服务发布，否则视为风险云服务，需要问题整改完成后重新进行发布评估。现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。

$\qquad$计算公式：DI值=5×严重问题数＋2×一般问题数，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。

输入描述

$\qquad$第一行输入$M$和$N$($M \le 100000$，$N \le 1000$)，使用空格分隔，M表示代表云服务阈值，N表示接下来有N行问题统计数据；

$\qquad$接下来输入一个$N∗4$的矩阵表，行内使用空格分隔，第一列$A_i$为服务节点，第二列$B_i$为$A_i$的父节点，如果$A_i$为云服务则无父节点，此时Bi用∗号表示($A_i$和$B_i$取值为字符串，$1 \le$字符串长度$≤5$，均由小写英文字母或∗号组成)，第三列$C_i$为问题级别（$C_i$取值为{0,1}，0表示严重问题，1表示一般问题），第四列$D_i$为该节点该级别的问题数量(Di≤1000)。

$\qquad$说明：输入保证只出现树的关系，不会出现连通图的情况。

输出描述

$\qquad$输出一个整数，表示风险云服务个数。

样例一

输入

40 12 
a * 0 2 
a * 1 2 
b a 0 3 
b a 1 5 
c a 1 3 
d a 0 1 
d a 1 3 
e b 0 2 
f * 0 8 
f * 1 10 
g f 1 2
h * 0 4

输出

2

解释

$\qquad$（a * 0 2）表示节点a有2个严重问题，*表示无父节点，即a为云服务。（b a 1 5）表示节点b有5个一般问题，b的父节点是a。可以看出，该样例有3个云服务a、f、h。云服务a的子节点有b、c、d、e，严重问题个数为2+3+0+1+2=82+3+0+1+2=8，一般问题个数为2+5+3+3+0=132+5+3+3+0=13，DI值=8∗5+13∗2=66>阈值40，故云服务a是风险云服务；云服务f严重问题个数为8+0=88+0=8，一般问题个数为10+2=1210+2=12，DI值=8∗5+12∗2=64>阈值40，故云服务f也是风险云服务；云服务h严重问题个数为44，一般问题个数为00，DI值=4∗5+0∗2=20<=阈值40，故云服务h不是风险云服务；因此该样例有2个风险云服务。

样例二

输入

50 10 
b a 1 5 
a * 0 2 
b a 0 3 
c a 1 3 
d a 0 1 
a * 1 2 
d a 1 3 
e b 0 2 
f b 1 1 
g c 1 2

输出

1

Limitation

1s, 1024KiB for each test case.