dfs-tree | wenLiu.vercel

Huawei20220923

Problem Description

A cloud storage service provider uses a master-slave model to ensure high availability. When the master node fails, the system automatically switches to the backup node. To maintain system stability, it is necessary to detect the service status and trigger a master-slave switch if needed.

The services in the storage system have dependency relationships; each service depends on at most one other service, and the dependency relationships do not form a cycle. When a service fails, its dependent service is also affected, which may cause more service failures.

The goal is to determine the detection order to minimize the impact of failures on the business. First, detect the service that has the greatest impact on the business. If the impacts are the same, detect in ascending order of node numbers.

Input Description

The first line contains a positive integer (n), representing the total number of business nodes (1 ≤ (n) ≤ 100000).
The next line contains (n) integers, where the (i)-th integer (f_i) represents that node (i) depends on (f_i) (0 ≤ (i) < (n)).
If (f_i = -1), it means node (i) has no dependencies.
The data guarantees (f_i $\not=$ i).

Output Description

Output a single line with (n) integers separated by spaces, representing the final detection order.

Example

Input

5-1 -1 1 2 3

Output

4 3 2 1 0

Idea: DFS + Sorting

(f_i) represents (i) depends on (f_i)
Abstract as edge (f_i $\rightarrow$ i)
Sorting rules:
- Different subtree sizes: the larger the subtree size, the greater the impact, and the higher the sorting priority
- Same subtree sizes: detect in ascending order of node numbers

import java.util.*;import java.util.stream.IntStream;public class Main {    static int n; // Number of nodes    static int[] w, f, d, p; // w: dependency array, f: number of child nodes array, d: in-degree array, p: node number array    static List<Integer>[] g; // Graph represented as adjacency list    // Depth-first search to calculate the number of child nodes for each node    public static int dfs(int u) {        f[u] = 1; // Each node itself counts as one        for (int x : g[u]) { // Traverse all child nodes            f[u] += dfs(x); // Recursively calculate the number of child nodes and accumulate        }        return f[u];    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        n = sc.nextInt(); // Input the number of nodes        w = new int[n]; // Dependency array        f = new int[n]; // Number of child nodes array        d = new int[n]; // In-degree array        p = new int[n]; // Node number array        g = new ArrayList[n]; // Initialize adjacency list        for (int i = 0; i < n; i++) {            w[i] = sc.nextInt(); // Input dependency nodes            g[i] = new ArrayList<>(); // Initialize the adjacency list for each node        }        // Build the adjacency list and in-degree array        for (int i = 0; i < n; i++) {            p[i] = i; // Initialize node number array            if (w[i] != -1) { // If the node has dependencies                d[i]++; // Increase in-degree                g[w[i]].add(i); // Add current node to the dependency node            }        }        // Perform DFS for all nodes with in-degree of 0        for (int i = 0; i < n; i++) {            if (d[i] == 0) {                dfs(i); // Calculate the number of child nodes for each node            }        }        // Convert node number array to Integer array for sorting        Integer[] pWrapper = IntStream.of(p).boxed().toArray(Integer[]::new);        // Sort by descending order of child nodes, if equal sort by ascending order of node numbers        Arrays.sort(pWrapper, (a, b) -> {            if (f[a] != f[b]) return f[a] > f[b] ? -1 : 1;            return a - b;        });        // Output the sorted node numbers        for (int i = 0; i < n; i++) {            System.out.print(pWrapper[i] + " ");        }    }}

mhy2023081302

Problem Description

Given a tree with (n) nodes and the root node numbered 1. You can add a new child node to a leaf node. After several operations, find the maximum number of nodes that are at a distance not exceeding (k) from the root.

Input Description

In the first line, a positive integer n represents the number of nodes in the tree, and k represents the distance not exceeding the root of the tree. The following (n-1) lines each contain two integers (u) and (v), representing an edge between nodes (u) and (v).

Output Description

An integer indicating the maximum number of nodes that are at a distance not exceeding (k) from the root after several operations.

example

input

4 2  1 2  1 3  1 4

output 7

ideas ：DFS+contribution method counting

Consider the contribution of each node to the answer: If the current node's distance from the root node, denoted as (d), satisfies (d < k), then increment the answer by 1.
Additionally, if the current node is a leaf node, it implies that we can add (k-d) nodes below this leaf node, forming a chain. Counting according to the above method will yield the desired result. Note that the given edges in the problem are undirected, so it requires creating two directed edges.

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

Given a tree with ( n ) nodes and a specified edge, find the length of the longest simple path that passes through this edge. A simple path's length is defined by the number of edges on the path.

Input Description

The first line contains an integer ( n ), the number of nodes in the tree.
The second line contains ( n-1 ) integers, where the ( i )-th integer ( $p_i$ ) indicates an edge between node ( i+1 ) and node ( $p_i$).
The third line contains two integers ( x ) and ( y ), representing the specified edge. It is guaranteed that this edge is part of the tree.

Constraints:

( 2 $\leq$ n $\leq$ 10^5 )
( 1 $\leq$ $p_i$ $\leq$ n )
( 1 $\leq$ x, y $\leq$ n )
( x $\neq$ y )

Output Description

Output a single integer, the length of the longest simple path that passes through the specified edge.

Example

Input

71 2 3 4 5 33 7

Output

The structure of this tree can be visualized as follows:

        1        |        2        |        3       /\      4  7     /         5      /  6

Paths passing through the edge 3→7 include:

From Node 7 to Node 3, then to Node 2, and finally to Node 1: 7 -> 3 -> 2 -> 1, with a total length of 3. From Node 7 to Node 3, then to Node 6: 7 -> 3 -> 6, with a total length of 2. From Node 7 to Node 3, then to Node 4, and finally to Node 5: 7 -> 3 -> 4 -> 5, with a total length of 3. The longest path among all paths passing through the edge 3→7 is 7 -> 3 -> 4 -> 5 -> 6, with a total length of 4.

So, the final output is 4.

Solution: Two DFS Traversals

The problem requires finding the longest path passing through the specified edge ( (a $\rightarrow$ b) ). We can achieve this by separately starting from ( a ) and ( b ) and solving for the following two longest paths:

The longest path ( d1 ) starting from ( a ) and not passing through ( b ).
The longest path ( d2 ) starting from ( b ) and not passing through ( a ).

The final answer is ( (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();        }    }}

meituan2023040805

Given a tree with ( n ) nodes, each node is painted in one of three colors: red, green, or blue.

A tree is called colorful if it contains at least one red node, one green node, and one blue node. Initially, the tree is colorful.

Now, you need to cut an edge of the tree such that both resulting trees are colorful. Count the number of ways to cut the tree to achieve this.

Input Description

The first line contains an integer ( n ), the number of nodes.
The second line contains ( n-1 ) integers ( p₂, p₃, ..., p_n ), indicating an edge between node ( i ) and node ( p_i ).
The third line is a string of length ( n ), where the ( i )th character represents the color of the ( i )th node. 'R' represents red, 'G' represents green, and 'B' represents blue.

The input data forms a tree, and the string contains only these three uppercase letters. ( 3 ≤ n ≤ 10^5 ).

Output Description

Output a single positive integer, representing the number of ways to cut the tree so that both resulting trees are colorful.

Example

Input:

71 2 3 1 5 5GBGRRBB

Output:

Approach

Construct the tree with node 1 as the root.
For each edge u-v, where v is a child of u, cutting the edge u-v splits the tree into:
- A subtree rooted at v
- The rest of the tree rooted at 1 excluding the subtree rooted at v
Count the number of RGB nodes in both parts.
Perform a DFS to count the RGB nodes in the subtree rooted at each node.
Perform another DFS to enumerate each edge as a potential cut point, counting the RGB nodes in both resulting parts.
Check if both parts are colorful (each containing at least one red, one green, and one blue node) and count the valid cuts.
Output the number of valid cuts.

Example Code

import java.util.*;public class Main {    static int ans;    // Get the index corresponding to the color character    public static int idx(char ch) {        if (ch == 'R') return 0;        else if (ch == 'G') return 1;        return 2;    }    // Check if two arrays have at least one non-zero value in each position and are different    public static boolean check(int[] A, int[] B) {        for (int i = 0; i < 3; ++i) {            if (A[i] == 0 || B[i] == A[i]) {                return false;            }        }        return true;    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        // Using adjacency list to represent the tree        List<List<Integer>> g = new ArrayList<>();        for (int i = 0; i < n; i++) {            g.add(new ArrayList<>());        }        // Build the adjacency list        for (int i = 2; i <= n; i++) {            int p = sc.nextInt();            g.get(i - 1).add(p - 1);            g.get(p - 1).add(i - 1);        }        // Read the colors of the nodes        String s = sc.next();        // Record the RGB count in the subtree rooted at each node        int[][] cnt = new int[n][3];        // First DFS to count RGB nodes in each subtree        dfs(0, -1, true, g, s, cnt);        ans = 0;        // Second DFS to count the valid cuts        dfs(0, -1, false, g, s, cnt);        // Print the result        System.out.println(ans);    }    // Depth-First Search    public static void dfs(int u, int fa, boolean first, List<List<Integer>> g, String s, int[][] cnt) {        for (int v : g.get(u)) {            if (v == fa) continue; // Avoid revisiting the parent node            dfs(v, u, first, g, s, cnt);            if (first) {                // Accumulate the RGB count in the subtree                for (int j = 0; j < 3; ++j) cnt[u][j] += cnt[v][j];            } else {                // If the cut makes both trees colorful, increment the answer                if (check(cnt[v], cnt[0])) ans += 1;            }        }        // Update the current node's RGB count        if (first) cnt[u][idx(s.charAt(u))] += 1;    }}