Editorial for Червената Шапчица


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: doncho

This problem is designed to test DFS and/or BFS skills.

The solution is as follows:

  1. Find a leave
  2. Calculate paths to each of the other leaves
  3. Select the leave with maximum path
    • This is one of the leaves from the searched path
    • Think why, hint: how many paths are there between 2 nodes in a tree?
  4. Calculate paths to each of the other nodes
  5. The maximum path is the answer

Both BFS and DFS can be used to calculate the paths

Sample solution in pseudo code

def bfs(vertex, graph):
    best = { path: 0, vertex: vertex }
    queue
    used

    enqueue (vertex, graph.weights[vertex])
    used.add(vertex);

    while queue not empty:
        (vertex, path) = dequeue()
        update best if neccessary

        for each neighbour of vertex:
            if neighbour is used:
                skip
            else:
                enqueue (neighbour, path + graph.weights[neighbour])
                mark neighbour as used

def getMaxPath(graph):
    start = get random leaf
    tempBest = bfs(start, graph)
    best = bfs(max(tempBest), graph)
    return best

CSharp

int GetMaxPathDfs()
{
    var leaf = this.FindLeaf();

    var tempBest = this.GetBestFrom(leaf, this.weights[leaf], -1);

    var best = this.GetBestFrom(tempBest.Node, this.weights[tempBest.Node], -1);

    return best.Path;
}

Result GetBestFrom(int node, int currentPath, int parent)
{
    var best = new Result(node, currentPath);

    this.nodes[node]
        .Where((next) => next != parent)
        .ToList()
        .ForEach((next) =>
        {
            var current = this.GetBestFrom(next, currentPath + this.weights[next], node);

            if (current.Path > best.Path)
            {
                best.Path = current.Path;
                best.Node = current.Node;
            }
        });

    return best;
}

JavaScript

DFS

getMaxPathDfs() {
    var getBestFrom = (node, currentPath, parent) => {
        // use node

        var best = {
            path: currentPath,
            node: node
        };

        this.nodes[node]
            .filter((next) => next !== parent)
            .forEach((next) => {
                var current = getBestFrom(next, currentPath + this.weights[next], node);

                if (current.path > best.path) {
                    best.path = current.path;
                    best.node = current.node;
                }
            });

        return best;
    };
    var node = this.nodes
        .slice(1)
        .findIndex((children) => {
            return children.length === 1;
        });

    node += 1;

    var best = getBestFrom(node, this.weights[node], -1);

    best = getBestFrom(best.node, this.weights[best.node], -1);
    return best.path;
}

BFS

getMaxPath() {
    var getBestFrom = (node) => {
        var used = new Set();
        var queue = new Queue();
        var paths = {};
        paths[node] = this.weights[node];

        queue.enqueue(node);
        used.add(node);

        while (!queue.isEmpty()) {
            var currentNode = queue.dequeue();

            this.nodes[currentNode]
                .filter((nextNode) => !used.has(nextNode))
                .forEach((nextNode) => {
                    used.add(nextNode);
                    queue.enqueue(nextNode);
                    paths[nextNode] = paths[currentNode] + this.weights[nextNode];
                });
        }

        var best = {
            path: -1,
            node: -1
        };

        for (var node in paths) {
            if (paths[node] > best.path) {
                best.path = paths[node];
                best.node = node;
            }
        }
        return best;
    };

    var node = this.nodes
        .slice(1)
        .findIndex((children) => {
            return children.length === 1;
        });

    node += 1;

    var best = getBestFrom(node, this.weights[node], -1);

    best = getBestFrom(best.node, this.weights[best.node], -1);
    return best.path;
}

Java

public class RedRidingHoodSolution {
    private static int n;
    private static int[] money;
    private static ArrayList<ArrayList<Integer>> graph;
    private static int maxMoney;
    private static int bestNode;

    public static void redRidingHood() throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(in.readLine());
        money = new int[n];
        graph = new ArrayList<>();
        String[] moneyStrings = in.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            money[i] = Integer.parseInt(moneyStrings[i]);
        }

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            String[] nodes = in.readLine().split(" ");
            int a = Integer.parseInt(nodes[0]) - 1;
            int b = Integer.parseInt(nodes[1]) - 1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        maxMoney = 0;
        bestNode = -1;
        dfs(0, -1, 0);

        maxMoney = 0;
        dfs(bestNode, -1, 0);
        System.out.println(maxMoney);
    }

    private static void dfs(int x, int prev, int tempMoney) {
        tempMoney += money[x];
        boolean hasNext = false;
        for (int i : graph.get(x)) {
            if (i != prev) {
                hasNext = true;
                dfs(i, x, tempMoney);
            }
        }
        if (!hasNext) {
            if (tempMoney > maxMoney) {
                maxMoney = tempMoney;
                bestNode = x;
            }
        }
    }
}

Comments

There are no comments at the moment.