dfs-tree

华为20220923

题目描述

有一家云存储服务提供商，他们的存储系统采用主从模式以确保高可用性。当主节点发生故障时，系统会自动切换到备用节点。为了保证系统的稳定性，需要检测服务状态，并在必要时触发主备切换。

存储系统中的服务有依赖关系，每个服务最多依赖一个其他服务，且依赖关系不成环。某个服务故障时，其依赖的服务也会受到影响，可能导致更多服务故障。

需要确定检测顺序，以最大限度减少故障对业务的影响。首先检测对业务影响最大的服务，如果影响相同，则按节点编号升序检测。

输入描述

第一行输入两个整数 (n)，代表业务节点总个数（1 ≤ (n) ≤ 100000）。
接下来一行输入 (n) 个整数，第 (i) 个整数 (f_i) 代表 (i) 依赖 (f_i)（0 ≤ (i) < (n)）。
若 (f_i) = -1，则表示节点 (i) 没有依赖。
数据保证 (f_i) ≠ (i)。

输出描述

一行输出 (n) 个整数，以空格隔开，代表最终的检测顺序。

示例

输入

5
-1 -1 1 2 3

输出

4 3 2 1 0

思路：DFS + 排序

• (f_i) 代表 (i) 依赖 (f_i)
• 抽象为 边 (f_i \rightarrow i)
• 排序规则：
  • 子树节点数不同：节点数多的影响大，排序靠前
  • 子树节点数相同：按节点编号升序检测

import java.util.*;
import java.util.stream.IntStream;

public class Main {
    static int n; // 节点总数
    static int[] w, f, d, p; // w: 依赖数组, f: 子节点数量数组, d: 入度数组, p: 节点编号数组
    static List<Integer>[] g; // 邻接表表示的图

    // 深度优先搜索计算每个节点的子节点数量
    public static int dfs(int u) {
        f[u] = 1; // 每个节点自身算一个
        for (int x : g[u]) { // 遍历所有子节点
            f[u] += dfs(x); // 递归计算子节点的数量并累加
        }
        return f[u];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 输入节点总数
        w = new int[n]; // 依赖数组
        f = new int[n]; // 子节点数量数组
        d = new int[n]; // 入度数组
        p = new int[n]; // 节点编号数组
        g = new ArrayList[n]; // 初始化邻接表
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt(); // 输入依赖节点
            g[i] = new ArrayList<>(); // 初始化每个节点的邻接表
        }

        // 构建图的邻接表和入度数组
        for (int i = 0; i < n; i++) {
            p[i] = i; // 初始化节点编号数组
            if (w[i] != -1) { // 如果节点有依赖
                d[i]++; // 增加入度
                g[w[i]].add(i); // 在依赖节点中添加当前节点
            }
        }

        // 对所有入度为0的节点进行DFS
        for (int i = 0; i < n; i++) {
            if (d[i] == 0) {
                dfs(i); // 计算每个节点的子节点数量
            }
        }

        // 将节点编号数组转换为Integer数组，以便进行排序
        Integer[] pWrapper = IntStream.of(p).boxed().toArray(Integer[]::new);

        // 根据子节点数量降序排序，如果子节点数量相同则按节点编号升序排序
        Arrays.sort(pWrapper, (a, b) -> {
            if (f[a] != f[b]) return f[a] > f[b] ? -1 : 1;
            return a - b;
        });

        // 输出排序后的节点编号
        for (int i = 0; i < n; i++) {
            System.out.print(pWrapper[i] + " ");
        }
    }
}

mhy2023081302

题目描述

给定一个有 (n) 个节点的树，树根编号为 1。你可以在叶子节点上添加新的儿子节点。经过若干次操作后，求距离树根不超过 (k) 的节点最多有多少个。

输入描述

第一行，一个正整数 (n) 表示树中节点的个数，(k) 表示距离不超过树根的距离。接下来的 (n-1) 行，每行包含两个整数 (u) 和 (v)，表示节点 (u) 和 (v) 之间有一条边。

输出描述

一个整数，表示若干次操作后距离树根不超过 (k) 的节点最大数量。

示例

输入

4 2  
1 2  
1 3  
1 4  

输出

7

思路：DFS + 贡献计数法

• 考虑每个节点对答案的贡献：如果当前节点距离根节点的距离 (d) 满足 (d < k)，则答案加1。
• 此外，如果当前节点是叶子节点，则可以在该叶子节点下添加 (k-d) 个节点，形成一条链。根据上述方法统计即可。注意题目给出的边是无向边，需要将其视为两条有向边。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @description: Program to perform a depth-first search (DFS) on a tree structure
 * to calculate a specific result based on node distances and a given threshold k.
 * The exact nature of the problem is inferred from the code structure.
 * Assumes nodes are numbered from 1 to n in the input.
 * 
 * Author: wenLiu
 * Created: 2024/5/23
 */
public class Main {

    static int n, k; // Number of nodes and threshold value k
    static List<List<Integer>> g; // Adjacency list for the graph (tree)

    static int[] d; // Array to store distances of nodes from the root
    static long res; // Result variable to store the final output

    public static void main(String[] args) throws IOException {
        // Reading input using BufferedReader for efficient input handling
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        
        // Reading number of nodes (n) and threshold value (k)
        n = Integer.parseInt(tokenizer.nextToken());
        k = Integer.parseInt(tokenizer.nextToken());

        // Initializing the adjacency list for n nodes
        g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<Integer>());
        }

        // Reading the edges of the tree
        for (int i = 1; i < n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
            int u = Integer.parseInt(stringTokenizer.nextToken()) - 1; // Node u
            int v = Integer.parseInt(stringTokenizer.nextToken()) - 1; // Node v
            g.get(u).add(v); // Adding edge u-v
            g.get(v).add(u); // Adding edge v-u (since it's an undirected graph)
        }

        // Initializing distance array with a large value (infinity)
        d = new int[n];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[0] = 0; // Distance of root node (assumed to be node 0) is 0
        res = 0; // Initializing result variable

        // Starting DFS from the root node (node 0) with no parent (-1)
        dfs(0, -1);

        // Output the final result
        System.out.println(res);
    }

    // Depth-first search function to explore the tree
    private static void dfs(int u, int p) {
        // If the distance of node u is less than or equal to k, increment result
        if (d[u] <= k) {
            res++;
        }

        // If node u is a leaf node and its distance is less than k,
        // add (k - d[u]) to the result
        if (u != 0 && g.get(u).size() == 1 && d[u] < k) {
            res += (k - d[u]);
        }

        // Traverse all adjacent nodes (children) of node u
        for (int v : g.get(u)) {
            // Skip the parent node to avoid cycling back
            if (v == p) {
                continue;
            }

            // Set the distance of node v and recursively call DFS
            d[v] = d[u] + 1;
            dfs(v, u);
        }
    }
}

meituan2023040802

题目描述

给定一棵有 ( n ) 个节点的树和一条指定的边，找到所有经过这条边的简单路径中最长的一条路径的长度。简单路径的长度定义为路径上的边的数量。

输入描述

• 第一行包含一个整数 ( n )，表示树的节点个数。
• 第二行包含 ( n-1 ) 个整数，其中第 ( i ) 个整数 ( p_i ) 表示节点 ( i+1 ) 和节点 ( p_i ) 之间有一条边。
• 第三行包含两个整数 ( x ) 和 ( y )，表示指定的边。保证这条边是树上的一条边。

约束条件：

• ( 2 <= n <= 10^5 )
• ( 1 <= p_i <= n )
• ( 1 <= x, y <= n )
• ( x ≠ y )

输出描述

输出一个整数，表示所有经过指定边的简单路径中最长的一条路径的长度。

示例

输入

7
1 2 3 4 5 3
3 7

输出

4

思路：两次DFS

题目要求的是经过指定边 ( a -> b ) 的最长路径。可以分别从 ( a ) 和 ( b ) 出发，求解以下两个最长路径：

1. 以 ( a ) 为起点且不经过 ( b ) 的最长路径 ( d1 )
2. 以 ( b ) 为起点且不经过 ( a ) 的最长路径 ( d2 )

最终的答案就是 ( d1 + d2 + 1 )。

import java.util.*;

public class Main {
private static Scanner scanner = new Scanner(System.in);

private static List<List<Integer>> g;
private static int[] f;

private static void dfs(int u, int fa) {
    f[u] = 0;
    for (int v : g.get(u)) {
        if (v == fa) continue;
        dfs(v, u);
        f[u] = Math.max(f[u], f[v] + 1);
    }
}

private static void solve() {
    int n = scanner.nextInt();
    g = new ArrayList<>();
    for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
    for (int i = 1; i < n; i++) {
        int x = scanner.nextInt(), y = i + 1;
        g.get(x).add(y);
        g.get(y).add(x);
    }
    int a = scanner.nextInt(), b = scanner.nextInt();
    f = new int[n + 1];
    dfs(a, b);
    int res = f[a];
    dfs(b, a);
    res += f[b];
    System.out.println(res + 1);
}

public static void main(String[] args) {
    int T = 1;
    while (T-- > 0) {
        solve();
    }
}

}